Pagini recente » Istoria paginii runda/tmp | Atasamentele paginii Clasament pregatire-oji-clasele-xi-xii | Monitorul de evaluare | Diferente pentru runda/lasm-baraj1 intre reviziile 1 si 2 | Cod sursa (job #2496317)
#include <bits/stdc++.h>
using namespace std;
struct dd
{
double x,y;
};
const double eps=1e-12;
double cp(dd a,dd b,dd c)
{
return(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
}
int ccw(dd a,dd b,dd c)
{
double ccp=cp(a,b,c);
if(ccp>=-eps)return 1;
return 0;
}
dd ll;
dd v[120005];
bool cmp(dd a ,dd b)
{
return ccw(ll,a,b);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i;
scanf("%d",&n);
scanf("%lf%lf",&ll.x,&ll.y);
v[0]=ll;
for(i=1;i<n;i++)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
if(fabs(ll.x-v[i].x)<=eps)
{
if(ll.y-v[i].y>=-eps)
ll=v[i],v[i]=v[0],v[0]=ll;
}
if(ll.x-v[i].x>=-eps)
{
ll=v[i],v[i]=v[0],v[0]=ll;
}
}
sort(v+1,v+n,cmp);
dd st[15];
st[1]=ll;
st[2]=v[1];
int cnt=2;
for(i=2;i<n;i++)
{
while(ccw(st[cnt-1],st[cnt],v[i])!=1&&cnt>=2)
--cnt;
st[++cnt]=v[i];
}
cout<<cnt<<endl;
for(i=1;i<=cnt;i++)
printf("%lf %lf\n",st[i].x,st[i].y);
return 0;
}