Cod sursa(job #2672362)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 13 noiembrie 2020 19:11:10
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
#define ld long double

using namespace std;

struct point {
    ld x, y;

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

ld det(point p1, point p2, point p3) {
    return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y -
           p1.y * p2.x - p2.y * p3.x - p3.y * p1.x;
}

int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");

    int n;
    cin >> n;
    vector < point > v(n);

    for (auto& it : v) 
        cin >> it.x >> it.y;

    int pos_min = min_element(v.begin(), v.end()) - v.begin();
    swap(v[pos_min], v[0]);

    sort(v.begin() + 1, v.end(), [&](const point& p1, const point& p2) {
        return (p1.x - v[0].x) * (p2.y - v[0].y) > (p1.y - v[0].y) * (p2.x - v[0].x);
    });

    vector < point > stack(n + 5);
    int top_stack = 1;
    stack[0] = v[0]; stack[1] = v[1];

    for (int i = 2; i < n; ++i) {
        while (top_stack > 0 and det(stack[top_stack - 1], v[i], stack[top_stack]) > 0)
            --top_stack;

        stack[++top_stack] = v[i];
    }

    cout << top_stack + 1 << '\n';
    for (int i = 0; i <= top_stack; ++i)
        cout << fixed << setprecision(12) << stack[i].x << ' ' << stack[i].y << '\n';

    return 0;
}