Pagini recente » Cod sursa (job #559062) | Cod sursa (job #2844102) | Cod sursa (job #3138993) | Cod sursa (job #2367010) | Cod sursa (job #1765794)
#include <cstdio>
#include <algorithm>
using namespace std;
const int nmax = 120005;
const double eps = 0.000000000001;
int N,st[nmax],top;
bool viz[nmax];
struct Pct
{
double x,y;
bool operator < (const Pct &A) const
{
return y < A.y;
}
};
Pct v[nmax];
inline double Prod(Pct A, Pct B, Pct C)
{
return -C.x*(B.y-A.y)-C.y*(A.x-B.x)-(B.x*A.y-A.x*B.y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i,semn;
scanf("%d",&N);
for(i = 1; i <= N; i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+N+1);
top = 2;
st[1] = 1, st[2] = 2;
semn = 1;
viz[2] = true;
for(i = 3; i; i+=semn)
{
if(viz[i]) continue;
while(top >= 2 && Prod(v[st[top-1]],v[st[top]],v[i]) <= eps)
{
viz[st[top]] = false;
top--;
}
st[++top] = i;
viz[i] = true;
if(i == N) semn = -1;
}
top--;
printf("%d\n",top);
for(i = 1; i <= top; i++)
printf("%lf %lf\n",v[st[i]].x ,v[st[i]].y);
return 0;
}