Cod sursa(job #800478)

Utilizator Teodor94Teodor Plop Teodor94 Data 21 octombrie 2012 18:42:06
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.21 kb
// 3 puncte (x1, y1), (x2, y2), (x3, y3)
// Daca (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) == 0, punctele sunt coliniare
// Daca > 0, drumul va "vira" la stanga
// Daca < 0, drumul va "vira" la dreapta
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 120005;
const double INF = 1000000005;
const double MIN = 0.00001;

struct infasuratoare{
    double x, y;
};

int n, nr;
vector<pair<double, double> > v;
infasuratoare stack[N];

int compare(double a, double b) {
    if (a - b > MIN)
        return 1;
    if (b - a > MIN)
        return -1;
    return 0;
}

bool comp(pair<double, double> a, pair<double, double> b) {
    if (compare( (v[0].second - a.second) * (v[0].first - b.first), (v[0].first - a.first) * (v[0].second - b.second) ) == - 1)
        return true;
    return false;
}

void read() {
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        double x, y;
        scanf("%lf %lf", &x, &y);

        v.push_back(make_pair(x, y));
    }
}

void set_points() {
    double ymin = INF;
    int pos;

    for (int i = 0; i < n; ++i)
        if (v[i].second < ymin) {
            ymin = v[i].second;
            pos = i;
        }

    swap(v[pos].first, v[0].first);
    swap(v[pos].second, v[0].second);

    sort(v.begin() + 1, v.end(), comp);
}

inline int turn(infasuratoare p1, infasuratoare p2, pair<double, double> p3) {
    return (p2.x - p1.x) * (p3.second - p1.y) - (p2.y - p1.y) * (p3.first - p1.x);
}

void solve() {
    nr = 1;
    stack[0].x = v[0].first;
    stack[0].y = v[0].second;
    stack[1].x = v[1].first;
    stack[1].y = v[1].second;

    for (int i = 2; i < n; ++i) {
        int res = turn(stack[nr - 1], stack[nr], v[i]);
        if (res >= 0) {
            stack[++nr].x = v[i].first;
            stack[nr].y = v[i].second;
            continue;
        }
        if (res < 0) {
            --nr;
            --i;
            continue;
        }
    }
}

void write() {
    printf("%d\n", nr + 1);

    for (int i = 0; i <= nr; ++i)
        printf("%lf %lf\n", stack[i].x, stack[i].y);
}

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

    read();

    set_points();

    solve();

    write();

    return 0;
}