Cod sursa(job #1921000)

Utilizator KusikaPasa Corneliu Kusika Data 10 martie 2017 11:00:49
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;

//MACROS
#define X first
#define Y second
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
typedef pair <double, double> PDD;

double cww(PDD a1, PDD a2, PDD a3) { return (a1.X - a2.X) * (a1.Y - a3.Y) - (a1.X - a3.X) * (a1.Y - a2.Y); }

PDD a[120120], st[120120];

int main() {
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
	//freopen("in.txt","r",stdin);

    int n, idx = 0;
	cin >> n;
    rep(i,0,n) {
        cin >> a[i].X >> a[i].Y;
        if (a[idx] > a[i]) idx = i;
    }
    swap(a[idx],a[0]);
    sort(a+1,a+n,[&](PDD v, PDD u) { return cww(a[0],v,u) < 0; });

    int sz = 1;
    st[0] = a[0], st[1] = a[1];
    rep(i,2,n) {
        while (sz && cww(st[sz-1],st[sz],a[i]) > 0) sz--;
        st[++sz] = a[i];
    }

    cout << sz+1 << "\n";
    while (sz >= 0) printf("%.10f %.10f\n",st[sz].X,st[sz].Y), sz--;
}