Pagini recente » Cod sursa (job #724557) | Cod sursa (job #3261263) | Cod sursa (job #1168059) | Cod sursa (job #2669383) | Cod sursa (job #3280427)
#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
double x, y;
struct punct
{
long double x, y;
friend bool operator<(const punct &a, const punct &b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
};
vector<punct> pct;
vector<punct> st;
double cwp(punct p, punct a, punct b)
{
return (a.x - p.x)*(b.y - p.y) - (b.x - p.x)*(a.y - p.y);
}
bool cmp(punct a, punct b)
{
return cwp(pct[1], a, b) < 0;
}
void convex()
{
st.push_back(pct[1]);
st.push_back(pct[2]);
int head = 2;
for(int i=3; i<=n; i++)
{
while(st.size() >= 2 && cwp(st[st.size()-2], st[st.size()-1], pct[i]) > 0)
st.pop_back();
st.push_back(pct[i]);
}
}
int main()
{
cin >> n;
pct.resize(n+1);
for(int i=1; i<=n; i++)
cin >> pct[i].x >> pct[i].y;
sort(pct.begin() + 1, pct.end());
sort(pct.begin() + 2, pct.end(), cmp);
convex();
cout << st.size() << '\n';
reverse(st.begin(), st.end());
for(auto i:st)
cout << fixed << setprecision(6) << i.x << " " << i.y << '\n';
return 0;
}