Pagini recente » Cod sursa (job #1405206) | Cod sursa (job #2983069) | Cod sursa (job #3190194) | Cod sursa (job #931297) | Cod sursa (job #1157234)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define inf 2000000005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct
{ double x,y; } p[120005];
double mnx,mny; int n,mnpos,st[120005],k;
bool eg(double a,double b)
{ return (fabs(a-b)<1e-9); }
bool comp(Punct a,Punct b)
{ double p1,p2;
p1=(a.y-mny)/(a.x-mnx);
p2=(b.y-mny)/(b.x-mnx);
if (eg(a.x,mnx))
{ p1=inf; if (eg(a.y,mny)) p1=inf+1; }
if (eg(b.x,mnx))
{ p2=inf; if (eg(b.y,mny)) p2=inf+1; }
return p1>p2;
}
double crossprod(Punct a,Punct b,Punct c)
{
return (double) a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
}
void Read()
{ int i;
f>>n;
mny=inf;
for(i=1;i<=n;i++)
{f>>p[i].x>>p[i].y;
if (p[i].x<mnx || (eg(p[i].x,mnx) && p[i].y<mny))
{mnx=p[i].x; mny=p[i].y; mnpos=i;}
}
}
void Solve()
{ int i;
k=2; st[1]=1; st[2]=2;
for(i=3;i<=n;i++)
{ while(k>1 && crossprod(p[st[k-1]],p[st[k]],p[i])>0)
k--;
k++; st[k]=i;
}
}
int main()
{ int i;
Read();
sort(p+1,p+n+1,comp);
Solve();
g<<k<<"\n";
for(i=k;i>=1;i--)
g<<fixed<<setprecision(6)<<p[st[i]].x<<" "<<p[st[i]].y<<"\n";
return 0;
}