Pagini recente » Cod sursa (job #178807) | Cod sursa (job #2498286) | Cod sursa (job #2936121) | Cod sursa (job #2986007) | Cod sursa (job #2358089)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const double epsil=1e-12;
struct punct
{
double x,y;
} M[125000];
bool viz[125000];
int Q[125000];
bool operator<(punct& a,punct& b)
{
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
double col(punct A, punct B, punct C)
{
return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
double a,b;
scanf("%lf %lf",&a,&b);
M[i].x=a;
M[i].y=b;
}
sort(M+1,M+n+1);
int l=2;
Q[1]=1;
Q[2]=2;
viz[2]=1;
for(int i=1; i<=n; i++)
{
if(viz[i])
continue;
else
{
while(l>=2 && col(M[Q[l-1]],M[Q[l]],M[i])<epsil)
viz[Q[l--]]=0;
Q[++l]=i;
viz[i]=1;
}
}
for(int i=n-1; i>=1; i--)
{
if(viz[i])
continue;
else
{
while(l>=2 && col(M[Q[l-1]],M[Q[l]],M[i])<epsil)
viz[Q[l--]]=0;
Q[++l]=i;
viz[i]=1;
}
}
printf("%d\n",l-1);
for(int i=2;i<l;i++)
{
printf("%f %f\n",M[Q[i]].x,M[Q[i]].y);
}
printf("%f %f\n",M[Q[1]].x,M[Q[1]].y);
}