Pagini recente » Cod sursa (job #3222654) | Cod sursa (job #1490701) | Cod sursa (job #700806) | Cod sursa (job #2651468) | Cod sursa (job #2544017)
#include <bits/stdc++.h>
#define PDD pair<double,double>
#define X first
#define Y second
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
PDD a[120001];
int Up[120001],vfU;
int Down[120001],vfD;
int panta(PDD a,PDD b,PDD c)
{
double m1=(b.Y-a.Y)/(b.X-a.X);
double m2=(c.Y-b.Y)/(c.X-b.X);
if(m1>m2)
return -1;
else
return 1;
}
int main()
{
in>>n;
for(int i=1;i<=n;i++)
in>>a[i].X>>a[i].Y;
sort(a+1,a+1+n);
Up[1]=1;Up[2]=2;vfU=2;
for(int i=3;i<=n;i++)
{
while( vfU>=2 && panta( a[ Up[ vfU-1 ] ], a[ Up[ vfU ] ], a[i])>0 )
vfU--;
Up[++vfU]=i;
}
Down[1]=1;Down[2]=2;vfD=2;
for(int i=3;i<=n;i++)
{
while( vfD>=2 && panta( a[ Down[ vfD-1 ] ], a[ Down[ vfD ] ], a[i])<0 )
vfD--;
Down[++vfD]=i;
}
out<<vfU+vfD-2<<'\n';
for(int i=vfU;i>=1;i--)
out<<setprecision(6)<<fixed<<a[ Up[i] ].X<<' '<<a[ Up[i] ].Y<<'\n';
for(int i=2;i<=vfD-1;i++)
out<<a[ Down[i] ].X<<' '<<a[ Down[i] ].Y<<'\n';
return 0;
}