Cod sursa(job #1608024)

Utilizator BrandonChris Luntraru Brandon Data 21 februarie 2016 19:30:00
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

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

class Point {
    public:
    double x, y;
};

vector <Point> stk;

Point point[120005];
int point_nr;

void read() {
    cin >> point_nr;
    for(int i = 1; i <= point_nr; ++i) {
        cin >> point[i].x >> point[i].y;
    }
}

inline double cross_product(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline bool cmp(Point a, Point b) {
    return cross_product(point[1], a, b) < 0;
}

void sort_point() {
    int pos = 1;
    for(int i = 1; i <= point_nr; ++i) {
        if(point[i].x < point[pos].x) {
            pos = i;
            continue;
        }
        if(point[i].y < point[pos].y) {
            pos = i;
        }
    }
    swap(point[1], point[pos]);
    sort(&point[2], &point[point_nr + 1], cmp);
}

void solve() {
    sort_point();
    stk.push_back(point[1]);
    stk.push_back(point[2]);
    for(int i = 3; i <= point_nr; ++i) {
        while(stk.size() > 2 and cross_product(stk[stk.size() - 1], stk[stk.size() - 2], point[i]) < 0) {
            stk.pop_back();
        }
        stk.push_back(point[i]);
    }
}

void print() {
    cout << fixed;
    cout << stk.size() << '\n';
    while(!stk.empty() ) {
        cout << setprecision(13) << stk[stk.size() - 1].x << ' ' << stk[stk.size() - 1].y << '\n';
        stk.pop_back();
    }
}

int main() {
    read();
    solve();
    print();
    return 0;
}