Cod sursa(job #1238726)

Utilizator SmarandaMaria Pandele Smaranda Data 7 octombrie 2014 16:50:40
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

struct Point {
    double x, y;
};

const double eps = 1.e-14;

Point ll;

int ccw (const Point &A, const Point &B, const Point &C) {
    double cp = ((double)B.x - A.x) * ((double)C.y - B.y) - ((double)B.y - A.y) * ((double)C.x - B.x);
    if (cp < 0)
        return -1;
    if (cp == 0)
        return 0;
    return 1;
}

double dist (const Point &A, const Point &B) {
    return ((double)A.x - B.x) * ((double)A.x - B.x) + ((double)A.y - B.y) * ((double)A.y - B.y);
}

class MyComp {
    public :
        bool operator () (const Point &A, const Point &B) {
            int cp;
            double d1, d2;
            cp = ccw (ll, A, B);
            if (cp == 0) {
                d1 = dist (ll, A);
                d2 = dist (ll, B);
                if (d1 - d2 <= -eps)
                    return 1;
                else return 0;
            }
            if (cp == -1)
                return 0;
            return 1;
        }
};

const int N = 100000;

Point P [N], H [N];
int n;

int main () {
    int i, poz, u, cp;
    Point aux;

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

    scanf ("%d", &n);
    ll.x = ll.y = 1000000000;
    for (i = 0; i < n; i ++)  {
        scanf ("%lf%lf", &P [i].x, &P [i].y);
        if (P [i].y - ll.y <= -eps || (fabs (P [i].y - ll.y) < eps && P [i].x - ll.x <= -eps)) {
            ll = P [i];
            poz = i;
        }
    }
    aux = P [0];
    P [0] = P [poz];
    P [poz] = aux;
    sort (P + 1, P + n, MyComp ());
    u = 0;
    H [++ u] = ll;
    H [++ u] = P [1];
    i = 2;
    while (i < n) {
        cp = ccw (H [u - 1], H [u], P [i]);
        if (cp > 0) {
            H [++ u] = P [i];
            ++ i;
        }
        else u --;
    }
    printf ("%d\n", u);
    for (i = 1; i <= u; i ++)
        printf ("%lf %lf\n", H [i].x, H [i].y);
    return 0;
}