Pagini recente » Cod sursa (job #1192512) | Cod sursa (job #1708712) | Cod sursa (job #1401567) | Cod sursa (job #879320) | Cod sursa (job #1745449)
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=120005, Eps=1e-12;
struct Point
{
double x,y;
} v[N];
bool cmp(Point a, Point b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
double cross_product(Point O, Point A, Point B) {
return (A.x-O.x)*(B.y-O.y)-(B.x-O.x)*(A.y-O.y);
}
int i,n,pos,r=1,st[N];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
sort(&v[1],&v[n+1],cmp);
st[1]=1, st[2]=2, pos=2;
for(i=3;i>0;i+=r)
{
if(i==n) r=-1;
while(pos>=2 and cross_product( v[st[pos-1]], v[st[pos]], v[i] ) < Eps )
pos--;
pos++;
st[pos]=i;
}
printf("%d\n",pos-1);
for(i=1;i<pos;i++) printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}