Pagini recente » Cod sursa (job #2750809) | Cod sursa (job #456488) | Utilizatori inregistrati la Fmi No Stress 9 | Cod sursa (job #1636584) | Cod sursa (job #2564109)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int NMAX=120005;
typedef pair<double,double>Point;
int n,head;
Point v[NMAX],st[NMAX];
inline void read()
{
f>>n;
for(int i=1; i<=n; i++)
f>>v[i].x>>v[i].y;
}
inline double cross_product(Point O,Point A,Point B)
{
return (A.x-O.x)*(B.y-O.y)-(B.x-O.x)*(A.y-O.y);
}
inline int cmp(const Point p1,const Point p2)
{
return cross_product(v[1],p1,p2)<0;
}
void sort_points()
{
int pos=1;
for(int i=2;i<=n;i++)
if(v[i]<v[pos])
pos=i;
swap(v[1],v[pos]);
sort(v+2,v+n+1,cmp);
}
inline void convex_hull()
{
sort_points();
st[1]=v[1];
st[2]=v[2];
head=2;
for(int i=3;i<=n;i++)
{
while(head>=2 && cross_product(st[head-1],st[head],v[i])>0)
head--;
st[++head]=v[i];
}
}
inline void write()
{
g<<head<<"\n"<<setprecision(6)<<fixed;
for(int i=head; i>=1; i--)
g<<st[i].x<<" "<<st[i].y<<"\n";
}
int main()
{
read();
convex_hull();
write();
return 0;
}