Cod sursa(job #711250)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("infasu.in");
ofstream fout("infasu.out");
typedef struct{double x,y;}cel;
int i,n,ninf=1,nsup=1;
vector <cel> inf;
vector <cel> sup;
double sarrus(cel a,cel b,cel c)
{ return (a.x*b.y)+(b.x*c.y)+(c.x*a.y)-(c.x*b.y)-(c.y*a.x)-(a.y*b.x);
}
int cmp(cel a,cel b)
{ if (a.x < b.x)
return 1;
else
return 0;
}
void citire()
{cel v[10001],pinf,psup;
int ipsup,ipinf;
fin >> n;
pinf.x = 1000000000;
psup.x = -1000000000;
for (i=1;i<=n;++i)
{ fin >> v[i].x >> v[i].y;
if (pinf.x > v[i].x)
{ pinf = v[i];
ipinf = i;
}
if (psup.x < v[i].x)
{ psup = v[i];
ipsup = i;
}
}
inf[1] = v[ipinf];
sup[1] = v[ipsup];
for (i=1;i<=n;++i)
if (i != ipinf && i != ipsup)
if (0 > sarrus(v[ipinf],v[ipsup],v[i]))
{ ++ninf;
inf[ninf] = v[i];
}
else
{ ++nsup;
sup[nsup] = v[i];
}
++nsup;
sup[nsup] = pinf;
++ninf;
inf[ninf] = psup;
sort(sup+1,sup+1+nsup,cmp);
sort(inf+1,inf+1+ninf,cmp);
}
void infasuratoare()
{int ok,i,j;
do
{ ok = 0;
i = 2;
while (i < nsup)
if (sarrus(sup[i-1],sup[i+1],sup[i]) > 0)
++i;
else
{ ok = 1;
for (j=i;j<=nsup;++j)
sup[j] = sup[j+1];
--nsup;
}
}while(ok);
do
{ ok = 0;
i = 2;
while (i < ninf)
if (sarrus(inf[i-1],inf[i+1],inf[i]) < 0)
++i;
else
{ ok = 1;
for (j=i;j<=ninf;++j)
inf[j] = inf[j+1];
--ninf;
}
}while(ok);
for (i=nsup-1;i>=2;--i)
{ ++ninf;
inf[ninf] = sup[i];
}
}
int main()
{ citire();
infasuratoare();
for (i=1;i<=ninf;++i)
fout << inf[i].x << " ";
fout << '\n';
for (i=1;i<=ninf;++i)
fout << inf[i].y << " ";
return 0;
}