Cod sursa(job #1116783)

Utilizator lucianRRuscanu Lucian lucianR Data 22 februarie 2014 20:16:36
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#define N_MAX 120010

using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

int N, x[N_MAX], y[N_MAX], ymin, nr = 1;

struct p {
    double x, y;
};

p v[100001], st[N_MAX/100], o = v[0];

bool cross(p a, p b, p c)
{
    return ((a.x-c.x) * (b.y-c.y) - (a.y-c.y) * (b.x-c.x) >= 0);
}

bool cmp(p a, p b)
{
    return cross(a, b, o);
}

int main()
{
    in >> N;
    for(int i = 0; i < N; i++)
    {
        in >> v[i].x >> v[i].y;
        //cout << v[i].x << v[i].y;
        if(v[i].y < v[ymin].y) ymin = i;
    }
    v[0] = v[ymin];
    sort(v, v + N, cmp);

    /*for(int i = 0; i < N; i++)
        cout << v[i].x << v[i].y << endl;*/

    st[0] = v[0];
    for(int i = 1; i < N; i++)
    {
        while(cross(v[i], st[nr], st[nr - 1]) && nr >= 1)
        {
            //cout << v[i].x << v[i].y << st[nr].x << st[nr].y << endl;
            nr--;
        }
        //cout << v[i].x << v[i].y << endl;
        st[++nr] = v[i];
    }
    out << nr + 1<< '\n';
    out << setprecision(15);
    for(int i = 0; i <= nr; i++)
        out << st[i].x << " " << st[i].y << endl;
    return 0;
}