Pagini recente » Cod sursa (job #2170432) | Cod sursa (job #1207175) | Cod sursa (job #682817) | Cod sursa (job #134647) | Cod sursa (job #363690)
Cod sursa(job #363690)
#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 ply=-A[pmin].y;
for (i=1; i<=n; i++) 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 vf=2;
for (i=3; i<=n; i++)
{
while (!det(B[S[vf-1]].x,B[S[vf-1]].y,B[S[vf]].x,B[S[vf]].y,B[i].x,B[i].y)) vf--;
S[++vf]=i;
}
printf("%d\n",vf);
for (i=1; i<=vf; i++) printf("%f %f\n",B[S[i]].x,B[S[i]].y-ply);
return 0;
}