Pagini recente » Cod sursa (job #1500783) | Cod sursa (job #2550110) | Cod sursa (job #276662) | Cod sursa (job #2942119) | Cod sursa (job #413704)
Cod sursa(job #413704)
#include<stdio.h>
#include<stdlib.h>
#define nmax 120004
struct asd {long double x; long double y;};
asd nod[nmax];
int n,i,j, index, db=0, que[nmax];
long double minx=9999999, miny=9999999, s;
int cmp(const void *a, const void *b)
{
return (((asd *)a)->y-miny)*(((asd *)b)->x-minx)>(((asd *)b)->y-miny)*(((asd *)a)->x-minx);
}
long double semn(int x1, int x2, int x3)
{
return nod[x1].x*nod[x2].y+nod[x2].x*nod[x3].y+nod[x3].x*nod[x1].y-nod[x2].x*nod[x1].y-nod[x3].x*nod[x2].y-nod[x1].x*nod[x3].y;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(i=0;i<n;i++)
{
scanf("%lf %lf", &nod[i].x, &nod[i].y);
if(nod[i].x<minx)
{
minx=nod[i].x;
miny=nod[i].y;
index=i;
}
else if(nod[i].x==minx&&nod[i].y<miny)
{
minx=nod[i].x;
miny=nod[i].y;
index=i;
}
}
qsort(nod, n, sizeof(asd), cmp);
que[++db]=1;
que[++db]=2;
for(i=3;i<n;i++)
{
s=semn(que[db-1], que[db], i);
if(s>0)
que[++db]=i;
else
{
while(semn(que[db-1], que[db], i)<0)
db--;
que[++db]=i;
}
}
que[++db]=0;
printf("%d\n", db);
for(i=1;i<=db;i++)
printf("%lf %lf\n", nod[i].x,nod[i].y);
return 0;
}