Cod sursa(job #1802957)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 10 noiembrie 2016 20:35:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int N = 120010, MAX = 1000000010;

int n, m, i, j, k, st[N], ind;

struct punct{
    double x, y;
} a[N], x, aux;

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

bool cmp(punct a, punct b) {
    double p1 = b.x * a.y;
    double p2 = a.x * b.y;
    if (p1 < p2) {
        return 1;
    }
    return 0;
}

int main() {
    x.x = MAX;
    x.y = MAX;
    fin >> n;
    for (i = 1; i <= n; ++i) {
        fin >> a[i].x >> a[i].y;
        if (a[i].y < x.y || (a[i].y == x.y && a[i].x < x.x))
            x = a[i], ind = i;
    }
    aux = a[ind];
    a[ind] = a[1];
    a[1] = aux;
    for (i = 1; i <= n; ++i) {
        a[i].x -= x.x, a[i].y -= x.y;
    }
    sort(a + 2, a + n + 1, cmp);
    st[1] = 1;
    st[2] = 2;
    k = 2;
    for (i = 3; i <= n; ++i) {
        while(k >= 2 && afla(a[st[k - 1]], a[st[k]], a[i]) < 0) {
            k--;
        }
        st[++k] = i;
    }
    fout << k << "\n" << fixed;
    for (i = 1; i <= k; ++i) {
        fout << setprecision(6) << a[st[i]].x + x.x << ' ' << a[st[i]].y + x.y << "\n";
    }
    return 0;
}