Cod sursa(job #2372001)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 6 martie 2019 20:48:12
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <iomanip>
#define ll long long
#define lsb(x) (x & -x)

using namespace std;

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

struct Point {
    long double x, y;

    bool operator< (const Point &other) const {
        if(x == other.x)
            return y < other.y;
        return x < other.x;
    }
};

long double det(const Point &a, const Point &b, const Point &c) {
    return (a.x * b.y + b.x * c.y + a.y * c.x - c.x * b.y - b.x * a.y - c.y * a.x);
}

Point start;
bool cmp(const Point &a, const Point &b) {
    return (det(start, a, b) < 0);
}

int main() {

    int n;
    in >> n;
    vector<Point> v(n + 1, {0, 0});
    for(int i = 1; i <= n; i ++)
        in >> v[i].x >> v[i].y;

    start = v[1];
    for(int i = 2; i <= n; i ++) {
        if(v[i] < start) {
            start = v[i];
            swap(v[1], v[i]);
        }
    }
    sort(v.begin() + 2, v.end(), cmp);

    vector<int> stk(n + 1, 0);
    int sz = 0;
    for(int i = 1; i <= n; i ++) {
        while(sz >= 2 && det(v[stk[sz - 1]], v[stk[sz]], v[i]) > 0)
            sz --;
        stk[++ sz] = i;
    }

    out << sz << "\n";
    for(int i = sz; i >= 1; i --)
        out << setprecision(12) << fixed << v[stk[i]].x << " " << v[stk[i]].y << "\n";

    return 0;
}