Cod sursa(job #1456123)

Utilizator retrogradLucian Bicsi retrograd Data 29 iunie 2015 20:33:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;
typedef long long var;

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

typedef pair<double, double> Point;
#define x first
#define y second

vector<Point> Points, Up, Dw;
#define UpS Up.size()
#define DwS Dw.size()


#define det(A, B, C) (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)

void Hull() {
    sort(Points.begin(), Points.end());

    for(auto &P : Points) {
        while(UpS >= 2 && det(Up[UpS-2], Up[UpS-1], P) >= 0)
            Up.pop_back();
        Up.push_back(P);

        while(DwS >= 2 && det(Dw[DwS-2], Dw[DwS-1], P) <= 0)
            Dw.pop_back();
        Dw.push_back(P);
    }
}

void Afis() {

    Dw.pop_back();
    reverse(Up.begin(), Up.end());
    Up.pop_back();

    fout<<fixed<<setprecision(12)<<UpS+DwS<<'\n';
    for(auto &P : Dw) fout<<P.x<<" "<<P.y<<'\n';
    for(auto &P : Up) fout<<P.x<<" "<<P.y<<'\n';
}

int main() {
    var n; double x, y;
    fin>>n;
    while(n--) {
        fin>>x>>y;
        Points.emplace_back(x, y);
    }
    Hull();
    Afis();
    return 0;
}