Pagini recente » Cod sursa (job #1586466) | Cod sursa (job #680321) | Cod sursa (job #312643) | Cod sursa (job #2933084) | Cod sursa (job #661868)
Cod sursa(job #661868)
# include <cstdio>
using namespace std;
int maix,n,i,pct;
double aux[2];
int pol[120005];
double p[120005][2];
double dot(double A[], double B[], double C[])
{
double AB[2];
double BC[2];
AB[0] = B[0]-A[0];
AB[1] = B[1]-A[1];
BC[0] = C[0]-B[0];
BC[1] = C[1]-B[1];
double d = AB[0] * BC[0] + AB[1] * BC[1];
return d;
}
double cross(double A[], double B[], double C[])
{
double AB[2];
double AC[2];
AB[0] = B[0]-A[0];
AB[1] = B[1]-A[1];
AC[0] = C[0]-A[0];
AC[1] = C[1]-A[1];
double c = AB[0] * AC[1] - AB[1] * AC[0];
return c;
}
int aranjare (int st, int dr);
void Qsort(int st, int dr);
int main ()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf("%d",&n);
maix=0;
for (i=0;i<n;i++)
{
scanf("%lf%lf",&p[i][0],&p[i][1]);
if (p[i][0]<p[maix][0])
maix=i;
else if (p[i][0]==p[maix][0]&&p[i][1]<p[i][1])
maix=i;
}
aux[0]=p[0][0];
aux[1]=p[0][1];
p[0][0]=p[maix][0];
p[0][1]=p[maix][1];
p[maix][0]=aux[0];
p[maix][1]=aux[1];
Qsort(1,n-1);
pct=2;
pol[0]=0;pol[1]=1;
for (i=2;i<n;i++)
{
while (cross(p[pol[pct-2]],p[pol[pct-1]],p[i])<0)
pct--;
pol[pct]=i;
pct++;
}
printf("%d\n",pct);
for (i=0;i<pct;i++)
printf("%lf %lf\n",p[pol[i]][0],p[pol[i]][1]);
return 0;
}
int aranjare (int st, int dr)
{
double aux[2];
aux[0]=p[st][0];
aux[1]=p[st][1];
while (st<dr)
{
while ((st<dr)&&(cross(p[0],aux,p[dr])>=0)) dr--;
if (st<dr)
{p[st][0]=p[dr][0];
p[st][1]=p[dr][1];}
while ((st<dr)&&(cross(p[0],aux,p[st])<=0)) st++;
if (st<dr)
{p[dr][0]=p[st][0];p[dr][1]=p[st][1];}
}
p[st][0]=aux[0];
p[st][1]=aux[1];
return st;
}
void Qsort (int st, int dr)
{
int poz;
if (st<dr)
{
poz=aranjare(st,dr);
Qsort(st,poz-1);
Qsort(poz+1,dr);
}
}