Cod sursa(job #1646508)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 10 martie 2016 16:27:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define MAXN 120000
using namespace std;

struct point{
    double x, y;
};
point P[MAXN + 1], st[MAXN + 1], pivot;
int n;

inline double sgn(point a, point b, point c) {
    return ((c.y - a.y) * (b.x - a.x)) - ((c.x - a.x) * (b.y - a.y));
}

inline bool cmp(point a, point b) {
    return sgn(P[0], a, b) < 0;
}

int main () {
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");

    cin >> n;
    for (int i = 0 ; i < n ; ++i)
        cin >> P[i].x >> P[i].y;
    pivot = P[0];
    int posp = 0;
    for (int i = 1 ; i < n ; ++i) {
        if (pivot.x < P[i].x || (pivot.x == P[i].x && pivot.y < P[i].y)) {
            pivot = P[i];
            posp = i;
        }
    }

    P[posp] = P[0];
    P[0] = pivot;
    sort(P + 1, P + n, cmp);

    st[0] = P[0];
    st[1] = P[1];
    int head = 1;

    for (int i = 2 ; i < n ; ++i) {
        while (head > 0 && sgn(st[head - 1], st[head], P[i]) >= 0) //?
            --head;
        st[++head] = P[i];
    }

    cout << fixed;
    cout << head + 1 << "\n";
    for (int i = head ; i >= 0 ; --i)
        cout << setprecision(9) << st[i].x << " " << st[i].y << "\n";
    return 0;
}