Cod sursa(job #1247415)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 22 octombrie 2014 19:32:55
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;

struct pt {
    double x, y;
};

int n;

const double eps = 1e-6;

bool comp(pt a, pt b) {
    return ((a.x + eps < b.x) || (a.x == b.x && a.y + eps < b.y));
}

bool cw(pt a, pt b, pt c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}

bool ccw(pt a, pt b, pt c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}

void convex_hull(vector <pt> &a) {
    if (a.size() == 1) return ;
    sort(a.begin(), a.end(), comp);
    pt p1 = a[0], p2 = a.back();
    vector <pt> up, down;
    up.pb(p1);
    down.pb(p1);
    for (size_t i = 1; i < a.size(); i++) {
        if (i == a.size() - 1 || cw(p1, a[i], p2)) {
            while (up.size() >= 2 && !cw(up[up.size() - 2], up[up.size() - 1], a[i]))
                up.pop_back();
            up.pb(a[i]);
        }
        if (i == a.size() - 1 || ccw(p1, a[i], p2)) {
            while (down.size() >= 2 && !ccw(down[down.size() - 2], down[down.size() - 1], a[i]))
                down.pop_back();
            down.pb(a[i]);
        }
    }
    a.clear();
    for (size_t i = 0; i < down.size(); i++)
        a.pb(down[i]);
    for (size_t i = up.size() - 2; i > 0; i--)
        a.pb(up[i]);
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    
    scanf("%d", &n);
    vector <pt> a;
    for (int i = 1; i <= n; i++)
    {
        pt curr;
        scanf("%lf%lf", &curr.x, &curr.y);
        a.pb(curr);
    }
    
    convex_hull(a);
    printf("%d\n", a.size());
    for (size_t i = 0; i < a.size(); i++)
        printf("%.8lf %.8lf\n", a[i].x, a[i].y);
    return 0;
}