Cod sursa(job #544818)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const char InFile[]="infasuratoare.in";
const char OutFile[]="infasuratoare.out";
const int MaxN=128000;
const double INF=1e250;
ifstream fin(InFile);
ofstream fout(OutFile);
struct s_point
{
s_point(double _x=0,double _y=0,double _ctg=0):x(_x),y(_y),ctg(_ctg){}
double x,y,ctg;
};
int N;
s_point p[MaxN];
vector<s_point> v;
struct cmp
{
inline bool operator() (const s_point &a, const s_point &b)
{
return a.ctg<b.ctg;
}
};
bool convex(s_point P1,s_point P2,s_point P3)
{
double X1=P1.x, Y1=P1.y;
double X2=P2.x, Y2=P2.y;
double X3=P3.x, Y3=P3.y;
double A=(X2-X1)*(Y3-Y1)-(X3-X1)*(Y2-Y1);
if(A<0)
{
return true;
}
return false;
}
void convex_hull(int N, s_point p[], vector<s_point> &v)
{
double xmin,ymin=INF;
int O;
for(register int i=1;i<=N;++i)
{
if(ymin>p[i].y)
{
ymin=p[i].y;
xmin=p[i].x;
O=i;
}
}
swap(p[O],p[1]);
for(register int i=2;i<=N;++i)
{
p[i].ctg=(p[i].x-xmin)/(p[i].y-ymin);
}
sort(p+2,p+N+1,cmp());
int ST[MaxN];
ST[0]=2;
ST[1]=1;
ST[2]=2;
for(register int i=3;i<=N;++i)
{
while(ST[0]>=2 && !convex(p[ST[ST[0]-1]],p[ST[ST[0]]],p[i]))
{
--ST[0];
}
ST[++ST[0]]=i;
}
v.clear();
for(register int i=1;i<=ST[0];++i)
{
v.push_back(s_point(p[ST[i]].x,p[ST[i]].y));
}
}
int main()
{
fin>>N;
for(register int i=1;i<=N;++i)
{
fin>>p[i].x>>p[i].y;
}
fin.close();
convex_hull(N,p,v);
fout<<v.size()<<"\n";
fout.precision(10);
fout.setf(ios::fixed,ios::floatfield);
for(vector<s_point>::iterator it=v.begin();it!=v.end();++it)
{
fout<<it->x<<" "<<it->y<<"\n";
}
fout.close();
return 0;
}