Pagini recente » Cod sursa (job #1371561) | Cod sursa (job #256221) | Cod sursa (job #3254754) | Cod sursa (job #2773369) | Cod sursa (job #1916361)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int nmax = 120005;
const double eps = -0.0000000000001;
int N,st[nmax],top;
bool viz[nmax];
struct point
{
double x,y;
bool operator < (const point &A)const
{
if(y == A.y) return x < A.x;
return y < A.y;
}
};
point v[nmax];
inline void Read()
{
int i;
fin >> N;
for(i = 1; i <= N; i++)
{
fin >> v[i].x >> v[i].y;
}
}
inline bool Delta(point A, point B, point C)
{
return ((A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y)) <= -eps);
}
inline void ConvexHull()
{
sort(v+1,v+N+1);
int i,semn;
st[++top] = 1;
st[++top] = 2;
viz[2] = true;
for(i = 3, semn = 1; i; i+=semn)
{
if(viz[i]) continue;
while(top >= 2 && Delta(v[st[top-1]],v[st[top]],v[i]))
{
viz[st[top--]] = false;
}
st[++top] = i;
viz[i] = true;
if(i == N) semn = -1;
}
top--;
fout << top << "\n";
for(i = 1; i <= top ; i++) fout << v[st[i]].x << " " << v[st[i]].y << "\n";
fout.close();
}
int main()
{
Read();
ConvexHull();
return 0;
}