Pagini recente » Cod sursa (job #414385) | Cod sursa (job #98450) | Cod sursa (job #789591) | Cod sursa (job #2678494) | Cod sursa (job #266994)
Cod sursa(job #266994)
#include<stdio.h>
#define ll long double
#include<stdlib.h>
#define Nmax 120000
#define EPS 1e-12
FILE*f=freopen("infasuratoare.in","r",stdin);
FILE*g=freopen("infasuratoare.out","w",stdout);
struct Punct
{
long double x,y;
};
Punct P[Nmax], v[Nmax], a[Nmax];
int n;
int comp(long double x, long double y)
{
if(x+EPS < y) return -1;
if(y+EPS < x) return +1;
return 0;
}
int cmp(const void *a, const void *b)
{
int i=*(int*)a, j=*(int*)b;
if(v[i].x == v[j].x) return v[i].y-v[j].y;
return v[i].x-v[j].x;
}
void sortare()
{
int ord[Nmax];
int i;
for(i=0;i<=n;++i) ord[i] = i;
P[0].x = P[1].y = -1000000003;
qsort(ord,n+1,sizeof(long int),cmp);
for(i=1;i<=n;++i) a[i] = v[ord[i]];
}
void read()
{
int i;
fscanf(f,"%d",&n);
for(i=1;i<=n;++i) fscanf(f,"%llf %llf",&v[i].x, &v[i].y);
}
inline int semn(Punct P1, Punct P2, Punct P3)
{
ll A = P3.x * (P1.y-P2.y);
ll B = P3.y * (P2.x-P1.x);
ll C = P1.x * P2.y - P2.x * P1.y;
return comp(A+B+C,0);
}
int uz[Nmax];
int H;
void convexHull()
{
int pas=+1, i=3, k=2, st[Nmax];
st[1] = 1; st[2] = 2; uz[2]=1;
while(!uz[1])
{
while(uz[i])
{
if(i==n) pas = -1;
i+=pas;
}
while(k>=2 && semn(a[st[k-1]], a[st[k]],a[i]) == -1) uz[st[k--]] = 0;
st[++k] = i; uz[i] = 1;
}
H = k - 1;
for(i=1;i<=H;++i) P[i] = a[st[i]];
}
void afisare()
{
int i;
fprintf(g,"%d\n",H);
for(i=1;i<=H;++i) fprintf(g,"%.6llf %.6llf\n",P[i].x,P[i].y);
}
int main()
{
read();
sortare();
convexHull();
afisare();
return 0;
}