Pagini recente » Cod sursa (job #392409) | Cod sursa (job #1881022) | Cod sursa (job #327926) | Cod sursa (job #1071081) | Cod sursa (job #363703)
Cod sursa(job #363703)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define inf 0x3f3f3f3f
#define N 120005
using namespace std;
struct coord
{
double x,y;
} A[N],B[N];
int ind[N],S[N];
double 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(double x1, double y1, double x2, double y2, double x3, double 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("%lf%lf",&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;
}
double 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);
for (i=1; A[ind[i]].x!=0 || A[ind[i]].y!=0; i++)
B[i]=A[ind[i]];
for (i++; A[ind[i]].x!=0 || A[ind[i]].y!=0; i++)
B[i-1]=A[ind[i]];
B[n].x=0; B[n].y=0;
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("%lf %lf\n",B[S[i]].x-plx,B[S[i]].y-ply);
return 0;
}