Cod sursa(job #1366772)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 1 martie 2015 13:42:10
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int maxn = 120005;

int n, minpos, st[maxn], top;
pair<double, double> p[maxn];

inline long double crossproduct(pair<double, double> a, pair<double, double> b, pair<double, double> c) {
    return 1LL * (b.first - a.first) * (c.second - a.second) - 1LL * (c.first - a.first) * (b.second - a.second);
}

struct classcomp {
    inline bool operator () (const pair<int, int> &a, const pair<int, int> &b) const {
        return crossproduct(p[1], a, b) < 0;
    }
};

int main() {
    fin >> n;
    minpos = 1;
    for(int i = 1 ; i <= n ; ++ i) {
        fin >> p[i].first >> p[i].second;
        if(p[i] < p[minpos])
            minpos = i;
    }
    swap(p[minpos], p[1]);
    minpos = 1;
    sort(p + 2, p + n + 1, classcomp());
    st[++ top] = 1;
    for(int i = 2 ; i <= n ; ++ i) {
        while(top >= 2 && crossproduct(p[i], p[st[top]], p[st[top - 1]]) < 0)
            -- top;
        st[++ top] = i;
    }
    fout << top << '\n';
    fout << fixed << setprecision(6);
    for(int i = top ; i >= 1 ; -- i)
        fout << p[st[i]].first << ' ' << p[st[i]].second << '\n';
}