Cod sursa(job #980690)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 5 august 2013 14:26:41
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define x first
#define y second

using namespace std;

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

const int N = 120010;
const int oo = (1 << 20);

int n, top = 2;
typedef pair <double, double> punct;
punct p[N], st[N], p0;

inline double Sign(punct p1, punct p2, punct p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);
}

inline bool cmp(const punct& a, const punct& b)
{
    return Sign(p0, a, b) < 0;
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>p[i].x>>p[i].y;

    int poz; double ord = oo, abs = oo;
    for(int i=1; i<=n; i++)
        if(p[i].y < ord) ord = p[i].y, poz = i; else
        if(p[i].y == ord && p[i].x < abs) abs = p[i].x, poz = i;

    p0 = p[poz];
    sort(p+1, p+n+1, cmp);
    st[1] = p[1]; st[2] = p[2];

    for(int i=3; i<=n; i++)
    {
        while(top > 1 && Sign(st[top-1], st[top], p[i]) > 0)
            top--;
        st[++top] = p[i];
    }
    fout<<top<<'\n';;
    fout<<fixed<<setprecision(6);
    for(int i=1; i<=top; i++)
        fout<<st[i].x<<' '<<st[i].y<<'\n';

    return 0;
}