Pagini recente » Cod sursa (job #2821461) | Cod sursa (job #866998) | Cod sursa (job #2450100) | Cod sursa (job #2163073) | Cod sursa (job #1537168)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,j,elements;
struct punct{float x,y;}v[120120],rez[120120];
int ff(punct a , punct b) {if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
double E(punct p, punct p2, punct p3)
{
return (p2.x - p.x) * (p3.y - p.y) - (p3.x - p.x)*(p2.y - p.y);
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,ff);
rez[1].x=v[1].x,rez[2].x=v[2].x,rez[1].y=v[1].y,rez[2].y=v[2].y;
elements=2;
for(i=3;i<=n;i++)
{
while(E(rez[elements-1],rez[elements],v[i])<=0 && elements>1)
elements--;
elements++;
rez[elements]=v[i];
}
elements++;
rez[elements]=v[n-1];
for(i=n-2;i>=1;i--)
{
while(E(rez[elements-1],rez[elements],v[i])<=0 && elements>1)
{elements--;
//cout<<E(rez[elements-1],rez[elements],v[i])<<endl;
}
elements++;
rez[elements]=v[i];
}
elements--;
g<<elements<<endl;
for(i=1;i<=elements;i++)
g<<fixed<<setprecision(6)<<rez[i].x<<" "<<rez[i].y<<endl;
}