Cod sursa(job #1456121)

Utilizator retrogradLucian Bicsi retrograd Data 29 iunie 2015 20:25:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 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;
var UpS, DwS;


double det(Point A, Point B, Point C) {
    B.x -= A.x; C.x -= A.x;
    B.y -= A.y; C.y -= A.y;

    return B.x * C.y - B.y * C.x;
}

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

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

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

void Afis() {
    fout<<fixed<<setprecision(12);
    fout<<UpS+DwS-2<<'\n';
    for(var i=0; i<Dw.size()-1; i++) fout<<Dw[i].first<<" "<<Dw[i].second<<'\n';
    for(var i=Up.size()-1; i>0; i--) fout<<Up[i].first<<" "<<Up[i].second<<'\n';
}

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