Cod sursa(job #661588)

Utilizator mihai995mihai995 mihai995 Data 14 ianuarie 2012 19:00:21
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <algorithm>
using namespace std;

const int N=120005;
struct Punct
{
    double x,y;
} v[2*N],a[N];
int n,m;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

inline bool cmp(const Punct &a,const Punct &b)
{
    return a.x<b.x || a.x==b.x && a.y<b.y;
}

inline bool panta(Punct A,Punct B,Punct C)
{
    return (B.y - A.y) * (C.x - A.x) < (B.x - A.x) * (C.y - A.y);
}

void del(Punct X)
{
    while (m>1 && panta(v[m-1],v[m],X))
        m--;
}

int main()
{
    int i;
    in>>n;
    for (i=1;i<=n;i++)
        in>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for (i=1;i<=n;i++)
    {
        del(a[i]);
        v[++m]=a[i];
    }
    for (i=n-1;i>1;i--)
    {
        del(a[i]);
        v[++m]=a[i];
    }
    del(a[1]);
    out<<m<<"\n";
    for (int i=1;i<=m;i++)
        out<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}