Pagini recente » Cod sursa (job #518423) | Cod sursa (job #2909186) | Cod sursa (job #320578) | Cod sursa (job #3134696) | Cod sursa (job #2576488)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
const int nmax=12e4;
int n, vf=2;
int hull[nmax+5];
struct punct
{
double x, y;
} P[nmax+5];
int cmp(punct a, punct b)
{
if(a.x<b.x)
return 1;
if(a.x==b.x)
return a.y<b.y;
return 0;
}
double det(punct a, punct b, punct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y;
}
int main()
{
fi>>n;
for(int i=1; i<=n; i++)
fi>>P[i].x>>P[i].y;
sort(P+1, P+n+1, cmp);
hull[1]=1;
hull[2]=2;
for(int i=3; i<=n; i++)
{
while(vf>=2 && det(P[hull[vf-1]], P[hull[vf]], P[i])<0)
vf--;
hull[++vf]=i;
}
for(int i=n-1; i>=1; i--)
{
while(vf>=2 && det(P[hull[vf-1]], P[hull[vf]], P[i])<0)
vf--;
hull[++vf]=i;
}
fo<<vf-1<<"\n";
for(int i=1; i<vf; i++)
fo<<fixed<<setprecision(12)<<P[hull[i]].x<<" "<<P[hull[i]].y<<"\n";
fi.close();
fo.close();
return 0;
}