Cod sursa(job #1497098)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 6 octombrie 2015 07:57:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iomanip>

using namespace std;

const int MULT = 2000000000;
const int XMAX = 1000000000;
const int NMAX = 120010;
const double Ep = 0.0000000000001;

struct punct {double x, y;};

punct v[NMAX];
int minim;
int N;
punct stiva[NMAX];
int h;

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


bool criteriu (punct a, punct b) {
    return determ (v[1], a, b) > 0;
}

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

int main () {
    freopen ("infasuratoare.in", "r", stdin);
    freopen ("infasuratoare.out", "w", stdout);

    fin >> N;
    minim = 0;
    v[0].x = v[0].y = MULT;
    for (int i = 1; i <= N; i++) {
        fin >> v[i].x >> v[i].y;

        if (v[i].x < v[minim].x) {
            minim = i;
        }
        else {
            if (v[i].x == v[minim].x && v[i].y < v[minim].y) {
                minim = i;
            }
        }
    }
    swap (v[minim], v[1]);
    sort (v + 2, v + N + 1, criteriu);

    stiva[1] = v[1];
    h = 1;
    for (int i = 2; i <= N; i++) {
        while (h > 1 && determ (stiva[h - 1], stiva[h], v[i]) <= 0) {
            h --;
        }

        stiva[++h] = v[i];
    }

    while (h > 1 && determ (stiva[h - 1], stiva[h], stiva[1]) <= 0) {
        h --;
    }
    fout << h << '\n';

    for (int i = 1; i <= h; i++) {
        fout << fixed << setprecision (12) << stiva[i].x << " " << stiva[i].y << '\n';
    }

    return 0;
}