Cod sursa(job #720058)

Utilizator deneoAdrian Craciun deneo Data 22 martie 2012 12:17:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define lung 200000

ifstream fin("infasuratoare.in");

struct point {
    double x, y;
};

int n, stiva[lung];
point p[lung];

bool cmp(point a, point b) {
    return (a.x - p[1].x) * (b.y - p[1].y) > (b.x - p[1].x) * (a.y - p[1].y);
}

double isLeft(int i1, int i2, int i3) {
    return p[i1].x * p[i2].y + p[i2].x * p[i3].y + p[i3].x * p[i1].y -
           p[i1].y * p[i2].x - p[i2].y * p[i3].x - p[i3].y * p[i1].x;
}

int main() {
    int i;
    fin >> n;
    freopen("infasuratoare.out", "w", stdout);
    for (i = 1; i <= n; ++i) {
        fin >> p[i].x >> p[i].y;
        if (p[i].x < p[1].x || (p[i].x == p[1].x && p[i].y < p[1].y))
            swap(p[1], p[i]);
    }
    sort(p + 2, p + n + 1, cmp);
    stiva[++stiva[0]] = 1;
    for (i = 2; i <= n; ++i) {
        while (stiva[0] >= 2 && (isLeft(stiva[stiva[0] - 1], stiva[stiva[0]], i) < 0))
            --stiva[0];
        stiva[++stiva[0]] = i;
    }
    printf("%d\n", stiva[0]);
    for (i = 1; i <= stiva[0]; ++i)
        printf("%f %f\n", p[stiva[i]].x, p[stiva[i]].y);
    return 0;
}