Cod sursa(job #661229)

Utilizator mihai995mihai995 mihai995 Data 14 ianuarie 2012 00:56:09
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 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 void dreapta(Punct A,Punct B,int &a,int &b,int &c)
{
    a = A.y - B.y;
    b = A.x - B.x;
    c = A.x * B.y - B.x * A.y;
}

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

inline double panta(Punct A,Punct B,Punct C)
{
    int a,b,c;
    dreapta(A,C,a,b,c);
    return a * B.x - b*B.y + c;
}

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++)
    {
        while (m>1 && panta(a[i],v[m],v[m-1])<0)
            m--;
        v[++m]=a[i];
    }
    for (i=n-1;i>1;i--)
    {
        while (m>1 && panta(a[i],v[m],v[m-1])>0)
            m--;
        v[++m]=a[i];
    }
    out<<m<<"\n";
    for (int i=1;i<=m;i++)
        out<<v[i].x<<" "<<v[i].y<<"\n";
    return 0;
}