Pagini recente » Cod sursa (job #3291121) | Cod sursa (job #642951)
Cod sursa(job #642951)
# include <stdio.h>
# define inf 1000000000.0
int i,n,pozz;
struct punct
{
double x,y;
}a[120005],px;
double panta (punct y)
{
if (px.x!=y.x)
return (y.y-px.y)/(y.x-px.x);
else
return inf;
}
int poz (int i,int j)
{
int ii=0,jj=-1;
punct aux;
while (i<j)
{
if (panta (a[i])>panta(a[j]))
{
aux=a[i];
a[i]=a[j];
a[j]=aux;
if (ii==1)
{
ii=0;
jj=-1;
}
else
{
ii=1;
jj=0;
}
}
i=i+ii;
j=j+jj;
}
return i;
}
void sort (int i,int j)
{
if (i<j)
{
int k=poz(i,j);
sort (i,k-1);
sort (k+1,j);
}
}
double det (punct x,punct y,punct z)
{
return y.x*z.y+z.x*x.y+x.x*y.y-y.x*x.y-z.x*y.y-z.y*x.x;
}
punct st[120005];
int main ()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf ("%i",&n);
for (i=1;i<=n;i++)
scanf ("%lf%lf",&a[i].x,&a[i].y);
px.x=inf;
px.y=inf;
for (i=1;i<=n;i++)
if (px.x>a[i].x)
{
px.x=a[i].x;
px.y=a[i].y;
pozz=i;
}
else
if (px.x==a[i].x)
if (px.y>a[i].y)
{
px.x=a[i].x;
px.y=a[i].y;
pozz=i;
}
for (i=pozz;i<n;i++)
a[i]=a[i+1];
n--;
sort (1,n);
int v=1;
st[v]=px;
v++;
st[v]=a[1];
for (i=2;i<=n;i++)
{
while (det (st[v-1],st[v],a[i])<0)
{
v--;
if (v==1)
break;
}
v++;
st[v]=a[i];
}
printf ("%i\n",v);
for (i=1;i<=v;i++)
printf ("%lf %lf\n",st[i].x,st[i].y);
return 0;
}