Cod sursa(job #2194746)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 14 aprilie 2018 12:16:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");

struct punct {
    double x,y;
}v[120007];

int stiva[120007],s,n,poz;

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

bool cmp (punct a, punct b) {
    return unghi(v[1],a,b) < 0;
}

int main (void) {
    in >> n;

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

    poz = 1;
    for (int i = 1; i <= n; i ++) {
        if (v[poz].x > v[i].x) {
            poz = i;
        }
        if (v[poz].x == v[i].x) {
            if (v[poz].y > v[i].y) {
                poz = i;
            }
        }
    }
    swap (v[poz], v[1]);

    sort (v+2,v+n+1,cmp);

    stiva[1] = 1;
    s = 1;
    stiva[2] = 2;
    s = 2;

    for (int i = 3; i <= n; i ++) {
        while (s > 2 && unghi(v[stiva[s-1]], v[stiva[s]], v[i]) > 0) {
            s --;
        }
        s ++;
        stiva[s] = i;
    }

    out << s <<"\n";
    for (int i = s; i >= 1; i --) {
        out << setprecision(9) << fixed << v[stiva[i]].x <<" "<<v[stiva[i]].y <<"\n";
    }

    return 0;
}