Pagini recente » Cod sursa (job #661108) | Cod sursa (job #2872050) | Cod sursa (job #694341) | Cod sursa (job #356667) | Cod sursa (job #363695)
Cod sursa(job #363695)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define inf 0x3f3f3f3f
#define N 120005
using namespace std;
struct coord
{
float x,y;
} A[N],B[N];
int ind[N],S[N];
float panta[N];
bool cmp(int i, int j)
{
if (panta[i]==panta[j])
{
if (A[i].x==0) return fabs(A[i].y)>fabs(A[j].y);
return fabs(A[i].x)>fabs(A[j].x);
}
return panta[i]<panta[j];
}
int det(float x1, float y1, float x2, float y2, float x3, float y3)
{
return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)>=0;
}
int main()
{
int n,i,pmin=1;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=1; i<=n; i++)
{
scanf("%f%f",&A[i].x,&A[i].y);
if (A[i].x<A[pmin].x || (A[i].x==A[pmin].x && A[i].y<A[pmin].y)) pmin=i;
ind[i]=i;
}
float plx=-A[pmin].x, ply=-A[pmin].y;
for (i=1; i<=n; i++) A[i].x+=plx, A[i].y+=ply;
for (i=1; i<=n; i++)
{
if (A[i].x==0)
{
if (A[i].y<0) panta[i]=-inf;
else panta[i]=inf;
}
else panta[i]=A[i].y/A[i].x;
}
sort(ind+1,ind+n+1,cmp);
B[1].x=0; B[1].y=0;
for (i=1; A[ind[i]].x || A[ind[i]].y; i++)
B[i+1]=A[ind[i]];
for (i++; A[ind[i]].x || A[ind[i]].y; i++)
B[i]=A[ind[i]];
S[1]=1; S[2]=2;
int p=2;
for (i=3; i<=n; i++)
{
while (p>1 && !det(B[S[p-1]].x,B[S[p-1]].y,B[S[p]].x,B[S[p]].y,B[i].x,B[i].y)) p--;
S[++p]=i;
}
printf("%d\n",p);
for (i=1; i<=p; i++) printf("%f %f\n",B[S[i]].x-plx,B[S[i]].y-ply);
return 0;
}