Cod sursa(job #1411191)

Utilizator zpaePopescu Andreea zpae Data 31 martie 2015 15:29:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#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";
}