Cod sursa(job #1165590)

Utilizator tudorv96Tudor Varan tudorv96 Data 2 aprilie 2014 19:26:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

vector <pair <double, double> > P, stiva;
int n, poz;

double cross(pair <double, double> A, pair <double, double> B, pair <double, double> C) {
    return (B.first - A.first) * (C.second - A.second) - (C.first - A.first) * (B.second - A.second);
}

bool cmp(pair <double, double> A, pair <double, double> B) {
    return cross (P[0], A, B) < 0;
}

int main() {
    freopen ("infasuratoare.in", "r", stdin);
    freopen ("infasuratoare.out", "w", stdout);
    scanf ("%d", &n);
    for (int i = 0; i < n; ++i) {
        double x, y;
        scanf ("%lf %lf", &x, &y);
        P.push_back (make_pair (x, y));
        if (P[i] < P[poz])
            poz = i;
    }
    swap (P[0], P[poz]);
    sort ((P.begin() + 1), P.end(), cmp);
    stiva.push_back (P[0]);
    stiva.push_back (P[1]);
    for (int i = 2; i < n; ++i) {
        while (stiva.size() > 1 && cross (stiva[stiva.size() - 2], stiva[stiva.size() - 1], P[i]) > 0)
            stiva.pop_back();
        stiva.push_back (P[i]);
    }
    printf ("%d\n", stiva.size());
    for (vector <pair <double, double> > :: reverse_iterator it = stiva.rbegin(); it != stiva.rend(); ++it)
        printf ("%.9lf %.9lf\n", it->first, it->second);
}