Cod sursa(job #1963435)

Utilizator razvandRazvan Dumitru razvand Data 12 aprilie 2017 15:34:12
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

pair<double, double> points[120003];
pair<double, double> st[120003];
int am;

double cross_product(pair<double, double> around, pair<double, double> a, pair<double, double> b) {
    return ((a.first-around.first)*(b.second-around.second)) - ((b.first-around.first)*(a.second-around.second));
}

bool cmp(pair<double, double> a, pair<double, double> b) {
    return cross_product(points[1], a, b) < 0;
}

int main() {

    int n;
    in >> n;
    int F = 1;

    for(int i = 1; i <= n; i++) {
        in >> points[i].first >> points[i].second;
        if(points[i] < points[F])
            F = i;
    }

    swap(points[1], points[F]);
    sort(points+2, points+n+1, cmp);

    st[1] = points[1];
    st[2] = points[2];
    am = 2;

    for(int i = 3; i <= n; i++) {
        while(am >= 2 && (cross_product(st[am-1], st[am], points[i]) > 0))
            am--;
        st[++am] = points[i];
    }

    out << am << '\n';

    for(int i = am; i >= 1; i--) {
        out << st[i].first << " " << st[i].second << '\n';
    }

    return 0;
}