Cod sursa(job #1497064)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 5 octombrie 2015 23:51:41
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 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 float Ep = 0.000000000001;

struct punct {float x, y;};

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

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

        return MULT;
    }
    return a.y / a.x;
}

bool criteriu (punct a, punct b) {
    if (abs (raport (a) - raport (b)) < Ep) {
        float da = sqrt (a.x * a.x + a.y * a.y);
        float db = sqrt (b.x * b.x + b.y + b.y);

        return da < db;
    }

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

float 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 ("%f%f", &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];
            }
        }
    }

    float transX, transY;
    transX = minim.x;
    transY = minim.y;
    minim.x = minim.y = 0;
    for (int i = 0; i <= N; i++) {
        v[i].x -= transX;
        v[i].y -= transY;
    }

    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 + transX, stiva[i].y + transY);
    }

    return 0;
}