Pagini recente » Cod sursa (job #537106) | Cod sursa (job #856371) | Cod sursa (job #1742811) | Cod sursa (job #2105908) | Cod sursa (job #1411191)
#include <cstdio>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
#define x first
#define y second
#define N 120005
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef pair<double, double> Point;
Point v[N],q[N];
int h,n;
inline double cross(const Point& A, const Point& B, const Point& C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
inline int rule(const Point& p1, const Point& p2)
{
return cross(v[1],p1,p2)<0;
}
int main()
{
int i,p=1;
in >> n;
for(i=1;i<=n;++i)
in>>v[i].x>>v[i].y;
for(i=2;i<=n;++i)
if(v[i]<v[p])
p=i;
swap(v[1],v[p]);
sort(v+2,v+n+1,rule);
q[1]=v[1];
q[2]=v[2];
h=2;
for(i=3;i<=n;++i)
{
while(h>=2&&cross(q[h-1],q[h],v[i])>0)
h--;
q[++h]=v[i];
}
out<<fixed<<h<<"\n";
for(i=h;i>=1;--i)
out<<setprecision(9)<<q[i].x<<" "<<q[i].y<<"\n";
}