Cod sursa(job #1522594)

Utilizator sebinechitasebi nechita sebinechita Data 11 noiembrie 2015 20:38:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define x first
#define y second
#define MAX 120010
#define eps 1e-12
typedef double ld;
pair<ld, ld> a[MAX];
int st[MAX], dr, viz[MAX];

ld cross_product(pair<ld, ld> o, pair<ld, ld> a, pair<ld, ld> b)
{
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

int main()
{
    int n, i, dr;
    fin >> n;
    for(i = 1 ; i <= n ; i++)
    {
        fin >> a[i].x >> a[i].y;
    }
    sort(a + 1, a + n + 1);
    dr = 0;
    st[++dr] = 1;
    st[++dr] = 2;
    viz[2] = 1;
    for(i = 3 ; i <= n ; i++)
    {
        while(dr >= 2 && cross_product(a[st[dr - 1]], a[st[dr]], a[i]) < eps)
        {
            viz[st[dr--]] = 0;
        }
        st[++dr] = i;
        viz[i] = 1;
    }
    for(i = n ; i >= 1 ; i--)
    {
        if(viz[i])
            continue;
        while(dr >= 2 && cross_product(a[st[dr - 1]], a[st[dr]], a[i]) < eps)
            viz[st[dr--]] = 0;
        st[++dr] = i;
        viz[i] = 1;
    }
    fout << dr - 1 << "\n";
    for(i = 2 ; i <= dr ; i ++)
    {
        fout << setprecision(6) << fixed << a[st[i]].x << " " << a[st[i]].y << "\n";
    }
}