Cod sursa(job #1837103)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 28 decembrie 2016 23:56:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const int NMAX = 121000;

int n;
pair <double, double> p[NMAX];

inline int Cross(int i, int j, int k) {
    double fi = (p[j].fi - p[i].fi) * (p[k].se - p[i].se);
    double se = (p[k].fi - p[i].fi) * (p[j].se - p[i].se);
    return (fi == se ? 0 : (fi < se ? -1 : 1));
}

int s[NMAX];
int ss;

vector <int> Convex(int l, int r) {
    vector <int> c;
    ss = 0;
    for (int i = l; i <= r; i++) {
        while (ss >= 2 && Cross(s[ss - 2], s[ss - 1], i) <= 0) {
            ss--;
        }
        s[ss++] = i;
    }
    for (int i = 0; i < ss - 1; i++) {
        c.push_back(s[i]);
    }
    ss = 0;
    for (int i = r; i >= l; i--) {
        while (ss >= 2 && Cross(s[ss - 2], s[ss - 1], i) <= 0) {
            ss--;
        }
        s[ss++] = i;
    }
    for (int i = 0; i < ss - 1; i++) {
        c.push_back(s[i]);
    }
    return c;
}

int main() {
    f >> n;
    for (int i = 1; i <= n; i++) {
        f >> p[i].fi >> p[i].se;
    }
    sort(p + 1, p + n + 1);
    vector <int> c = Convex(1, n);
    g << c.size() << "\n";
    g << setprecision(12) << fixed;
    for (int i: c) {
        g << p[i].fi << " " << p[i].se << "\n";
    }
}