Pagini recente » Cod sursa (job #879247) | Cod sursa (job #1940114) | Cod sursa (job #1383945) | Cod sursa (job #2112554) | Cod sursa (job #2284042)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define INF 1000000006
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
double x, y;
}v[120005], a, s[120005];
int n, vf;
bool cmp(point b, point c)
{
double x=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
if(x==0) return b.y<c.y||(b.y==c.y&&b.x<c.x);
else return x<0;
}
int main()
{
a.x=INF, a.y=INF;
fin>>n;
for(int i=1;i<=n;++i)
{
fin>>v[i].x>>v[i].y;
if(v[i].y<a.y) a=v[i];
else if(v[i].y==a.y&&v[i].x<a.x) a=v[i];
}
sort(v+1, v+n+1, cmp);
v[n+1]=v[1], v[n+2]=v[2];
a=v[1];
point b=v[2], c=v[3];
s[++vf]=v[1];
s[++vf]=v[2];
int nr=0;
for(int i=3;i<=n+2;++i)
{
a=s[vf-1], b=s[vf], c=v[i];
if(!cmp(b, c)) s[vf]=c;
else s[++vf]=c, nr++;
}
fout<<nr<<"\n";
fout<<fixed;
for(int i=vf-1;i>=vf-nr+1;--i) fout<<setprecision(12)<<s[i].x<<" "<<setprecision(12)<<s[i].y<<"\n";
fout<<setprecision(12)<<s[vf].x<<" "<<setprecision(12)<<s[vf].y<<"\n";
return 0;
}