Cod sursa(job #1497094)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 6 octombrie 2015 07:42:45
Problema Infasuratoare convexa Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.98 kb
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>

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], minim;
int N;
punct stiva[NMAX];
int h;

double raport (punct a) {
    if (a.x == 0) {
        if (a.y < 0) {
            return -MULT;
        }

        return MULT;
    }
    return (a.y - minim.y) / (a.x - minim.x);
}

bool criteriu (punct a, punct b) {
    a.x -= minim.x; b.x -= minim.x;
    a.y -= minim.y; b.y -= minim.y;

    if (abs (raport (a) - raport (b)) < Ep) {
        double da = sqrt (a.x * a.x + a.y * a.y);
        double db = sqrt (b.x * b.x + b.y + b.y);

        return da < db;
    }

    return raport (a) < raport (b);
}

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;
}

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

    scanf ("%d", &N);
    minim.x = minim.y = MULT;
    for (int i = 1; i <= N; i++) {
        scanf ("%lf%lf", &v[i].x, &v[i].y);

        if (v[i].x < minim.x) {
            minim = v[i];
        }
        else {
            if (v[i].x == minim.x && v[i].y < minim.y) {
                minim = v[i];
            }
        }
    }

    sort (v + 1, v + N + 1, criteriu);

    stiva[1] = minim;
    h = 1;
    for (int i = 1; i <= N; i++) {
        if (v[i].x == minim.x && v[i].y == minim.y) {
            continue;
        }

        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 --;
    }
    printf ("%d\n", h);

    for (int i = 1; i <= h; i++) {
        printf ("%f %f\n", stiva[i].x, stiva[i].y);
    }

    return 0;
}