Cod sursa(job #1608445)

Utilizator BrandonChris Luntraru Brandon Data 22 februarie 2016 08:56:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 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 = 2; i <= point_nr; ++i) {
        if(point[i].x > point[pos].x) {
            continue;
        }
        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() - 2], stk[stk.size() - 1], 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;
}
/*
8
-14.000000 -6.000000
-12.000000 -11.000000
7.000000 -13.000000
12.000000 -1.000000
12.000000 1.000000
11.000000 7.000000
3.000000 11.000000
-8.000000 12.000000
*/