Cod sursa(job #1596374)

Utilizator andytosaAndrei Tosa andytosa Data 10 februarie 2016 22:40:21
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

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

struct punct{
    double x, y;
};
punct v[120005], inf[120005];
int n, poz;

bool comp(punct a, punct b){
    if(a.x < b.x)
        return true;
    if(a.x == b.y && a.y < b.y)
        return true;
    return false;
}

double sarrus(punct a, punct b, punct c){
    return a.x * b.y + a.y * c.x + b.x * c.y - c.x * b.y - b.x * a.y - a.x * c.y;
}

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

    sort(v + 1, v + 1 + n, comp);

    for(int i = 1; i <= n; ++i){
        while(poz >= 2 && sarrus(inf[poz - 1], inf[poz], v[i]) >= 0)
            poz--;
        poz++;
        inf[poz] = v[i];
    }
    int nr1 = poz;
    for(int i = n - 1; i >= 1; --i){
        while(poz > nr1 && sarrus(inf[poz - 1], inf[poz], v[i]) >= 0)
            poz--;
        poz++;
        inf[poz] = v[i];
    }

    fout << poz - 1 <<'\n';
    fout << fixed;
    for(int i = poz - 1; i >= 1; --i)
        fout << setprecision(6) << inf[i].x << ' ' << inf[i].y << '\n';
    return 0;
}