Pagini recente » Cod sursa (job #3280683) | Cod sursa (job #2405571) | Cod sursa (job #1912962) | Cod sursa (job #1877116) | Cod sursa (job #390380)
Cod sursa(job #390380)
#include <cstdio>
#include <math.h>
#include <algorithm>
#define MaxN 120024
struct punct{
double x,y,cos;
} a[MaxN];
int N,M,min,sol[MaxN];
int cmp(punct x,punct y)
{
return x.cos>y.cos;
}
void read()
{
int i;
punct aux;
freopen("infasuratoare.in","r",stdin);
scanf("%d",&N);
scanf("%lf %lf",&a[1].x,&a[1].y);
a[1].cos=a[1].x/sqrt(a[1].y*a[1].y+a[i].x*a[i].x);
min=1;
for(i=2;i<=N;i++)
{
scanf("%lf %lf",&a[i].x,&a[i].y);
a[i].cos=a[i].x/sqrt(a[i].y*a[i].y+a[i].x*a[i].x);
if(a[i].x<a[min].x || (a[i].x==a[min].x && a[i].y<a[min].y))
min=i;
}
aux=a[1]; a[1]=a[min]; a[min]=aux;
}
double delta(punct p1,punct p2,punct p3)
{
return p1.x*p2.y+p2.x*p3.y+p1.y*p3.x-p3.x*p2.y-p3.y*p1.x-p2.x*p1.y;
}
void scanare()
{
int i;
double d;
sol[1]=1; sol[2]=2; sol[3]=3;
M=3;
for(i=4;i<=N;i++)
{
d=delta(a[sol[M-1]],a[sol[M]],a[i]);
while(d<0 && M>=2)
{
M--;
d=delta(a[sol[M-1]],a[sol[M]],a[i]);
}
sol[++M]=i;
}
}
void write()
{
int i;
freopen("infasuratoare.out","w",stdout);
printf("%d\n",M);
for(i=1;i<=M;i++)
printf("%lf %lf\n",a[sol[i]].x,a[sol[i]].y);
}
int main()
{
read();
std::sort(a+2,a+N+1,cmp);
scanare();
write();
return 0;
}