Cod sursa(job #1970440)

Utilizator bt.panteaPantea Beniamin bt.pantea Data 19 aprilie 2017 12:38:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
Raporteaza aceasta sursa 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <bitset>
#define NMAX 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair<double, double> P;
const double EPS = 1e-12;
int n;
pair<double, double> v[NMAX];
bitset < NMAX > vis;
int st[NMAX], head;
inline void Read() {
    f>>n;
    for (int i = 1; i <= n; i++)
        f>>v[i].first>>v[i].second;
}
inline double cross_product(P o, P a, P b) {
    return (a.first - o.first) * (b.second - o.second) - (b.first - o.first) * (a.second - o.second);
}

inline void convex() {
    sort(v + 1, v + 1 + n);
    st[1] = 1; st[2] = 2; head = 2;
    vis[2] = 1;
    for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p))) {
        if (vis[i]) continue;
        while(head >= 2 && cross_product(v[st[head - 1]], v[st[head]], v[i]) < EPS)
            vis[st[head--]] = 0;
        st[++head] = i;
        vis[i] = 1;
    }
    g<<head - 1<<'\n';
    g<<setprecision(6)<<fixed;
    for (int i = 1; i < head; i++)
        g<<v[st[i]].first<<' '<<v[st[i]].second<<'\n';
}

int main()
{
    Read();
    convex();
    return 0;
}