Cod sursa(job #932757)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 29 martie 2013 11:05:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <algorithm>
#define MAX_N 120010

using namespace std;

struct punct {
    double x, y;
} v[MAX_N];

int n, h, s[MAX_N];

int cmp (punct a, punct b) {
    return (a.y - v[0].y) * (b.x - v[0].x) > (b.y - v[0].y) * (a.x - v[0].x);
}

double semn (int i, int j, int k) {
    return (v[i].y - v[j].y) * v[k].x + (v[j].x - v[i].x) * v[k].y + v[i].x * v[j].y - v[j].x * v[i].y;
}

int main()
{
    freopen ("infasuratoare.in","r",stdin);
    freopen ("infasuratoare.out","w",stdout);
    scanf ("%d", &n);
    int i, p;
    for (i = 0; i < n; i++) scanf ("%lf %lf", &v[i].x, &v[i].y);
    p = 0;
    for (i = 1; i < n; i++)
        if (v[i].x < v[p].x || (v[i].x == v[p].x && v[i].y < v[p].y)) p = i;
    swap (v[0], v[p]);
    sort (v + 1, v + n, cmp);
    for (i = 0; i < n; i++) {
        while (h > 2 && semn (s[h-1], s[h], i) >= 0) h--;
        s[++h] = i;
    }
    printf ("%d\n", h);
    for (i = h; i > 0; i--) printf ("%lf %lf\n", v[s[i]].x, v[s[i]].y);
    return 0;
}