Cod sursa(job #1647629)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 10 martie 2016 21:25:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 120005
#define eps 1e-12

struct point {
    double x;
    double y;
};

struct line {
    double a;
    double b;
    double c;
};

point p[NMAX];
point hull[NMAX];
point st[NMAX];
int n, k;

bool point_sort(point a, point b) {
    return a.y < b.y;
}

inline int cmp(double a, double b) {
    double c = a - b;
    if(c < -eps) return -1;
    if(c > eps) return 1;
    return 0;
}

inline line get_line(point p1, point p2) {
    line l;
    l.a = p1.y - p2.y;
    l.b = p2.x - p1.x;
    l.c = p1.x * p2.y - p2.x * p1.y;
    return l;
}

int side(line l, point p) {
    return cmp(l.a * p.x + l.b * p.y, -l.c);
}

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

    int i, j;

    scanf("%d", &n);
    for(i = 1; i <= n; i++) {
        scanf("%lf %lf", &p[i].x, &p[i].y);
    }

    sort(p+1, p+n+1, point_sort);

    st[1] = p[1];
    st[2] = p[2];
    k = 2;
    for(i = 3; i <= n; i++) {
        while(k >= 2 && side(get_line(st[k - 1], st[k]), p[i]) <= 0) {
            k--;
        }
        st[++k] = p[i];
    }
    j = 0;
    for(i = 1; i < k; i++) {
        hull[++j] = st[i];
    }

    st[1] = p[n];
    st[2] = p[n - 1];
    k = 2;
    for(i = n - 2; i > 0; i--) {
        while(k >= 2 && side(get_line(st[k - 1], st[k]), p[i]) <= 0) {
            k--;
        }
        st[++k] = p[i];
    }
    for(i = 1; i < k; i++) {
        hull[++j] = st[i];
    }

    printf("%d\n", j);
    for(i = 1; i <= j; i++) {
        printf("%f %f\n", hull[i].x, hull[i].y);
    }

    return 0;
}