Pagini recente » Cod sursa (job #1866765) | Cod sursa (job #1158991) | Cod sursa (job #2563006) | Cod sursa (job #533157) | Cod sursa (job #348952)
Cod sursa(job #348952)
#include<stdio.h>
#include<algorithm>
using namespace std;
int i,n,d,sor[12010],stiva[12010];
struct point
{ long double x,y;
}p[120010],q;
inline long double isleft(point a, point b, point c)
{ return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool comp( int i, int j)
{ if( isleft( p[0],p[i],p[j])>0) return 1;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
scanf("%LE %LE",&p[0].x,&p[0].y);
q=p[0];
for(i=1;i<n;i++) { scanf("%LE %LE",&p[i].x,&p[i].y);
if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x>p[0].x)) { q=p[i];
p[i]=p[0];
p[0]=q;
}
sor[i]=i;
}
p[n]=p[0];
p[n+1]=p[1];
sort(sor+1,sor+n,comp);
for(i=1;i<n;i++) { while(d>0&&isleft(p[stiva[d-1]],p[stiva[d]],p[sor[i]])<=0) d--;
stiva[++d]=sor[i];
}
printf("%d\n",d+1);
for(i=0;i<=d;i++) printf("%LE %LE\n",p[stiva[i]].x,p[stiva[i]].y);
fclose(stdin);
fclose(stdout);
return 0;
}