Pagini recente » Cod sursa (job #2549312) | Cod sursa (job #2041710) | Cod sursa (job #984110) | Cod sursa (job #148199) | Cod sursa (job #2194116)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1.e-14;
struct dd
{
double x,y;
}ll;
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 r=cp(a,b,c);
if(r<-eps)return -1;
return 1;
}
bool cmp(dd a,dd b)
{
int s=ccw(ll,a,b);
if(s>0)return 1;
return 0;
}
dd a[120005];
dd v[120005];
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);
a[0]=ll;
for(i=1;i<n;i++)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
if(fabs(ll.y-a[i].y)<eps)
{
if(ll.x-a[i].x>=eps)
{
ll=a[i];
a[i]=a[0];
a[0]=ll;
}
continue;
}
if(ll.y-a[i].y>=eps)
{
ll=a[i];
a[i]=a[0];
a[0]=ll;
}
}
sort(a+1,a+n,cmp);
int cnt=2;
v[1]=ll;
v[2]=a[1];
for(i=2;i<n;i++)
{
dd t1=v[cnt-1],t2=v[cnt];
while(ccw(t1,t2,a[i])<0)
{
--cnt;
t1=v[cnt-1],t2=v[cnt];
}
cnt++;
v[cnt]=a[i];
}
printf("%d\n",cnt);
for(i=1;i<=cnt;i++)
printf("%f %f\n",v[i].x,v[i].y);
return 0;
}