Cod sursa(job #2203283)

Utilizator pentruoji2019Insane in corpore sano pentruoji2019 Data 11 mai 2018 19:50:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
 
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
 
#define NMAX 120005
#define pd pair<double, double>
 
pd v[NMAX];
pd st[NMAX];
 
inline double sinABC(pd A, pd B, pd C) {
    return ((C.second - B.second) * (A.first - B.first) -
        (C.first - B.first) * (A.second - B.second));
}
 
inline bool cmp(pd a, pd b) {
    return (sinABC(a, v[1], b) > 0);
}
 
int main() {
    int i, n;
 
    f >> n;
    for (i = 1; i <= n; ++i)
        f >> v[i].first >> v[i].second;
 
    int pos = 1;
    for (i = 2; i <= n; ++i)
        if (v[i] < v[pos])
            pos = i;
    swap(v[1], v[pos]);
 
    sort(v + 2, v + n + 1, cmp);
     
    int len = 2;
    st[1] = v[1];
    st[2] = v[2];
 
    for (i = 3; i <= n; ++i) {
        while (len >= 2 && sinABC(st[len - 1], st[len], v[i]) > 0)
            --len;
        st[++len] = v[i];
    }
 
    g << len << '\n';
    for (i = 1; i <= len; ++i) {
        g << fixed << setprecision(6) << st[i].first << ' ' << st[i].second << '\n';
    }
 
    return 0;
}