Cod sursa(job #2476046)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 17 octombrie 2019 22:19:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
#include <iomanip>

using namespace std;

struct Point
{
    double x, y;

    Point operator+(const Point& p) const {
        return {x + p.x, y + p.y};
    }

    Point operator-() const {
        return {-x, -y};
    }

    Point operator-(const Point& p) const {
        return {x - p.x, y - p.y};
    }
} v[120010], st[120010];

double cross(const Point& a, const Point& b)
{
    return a.x * b.y - a.y * b.x;
}

int main() {
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    int n;
    cin >> n;
    int leftbottomIdx = 0;
    for(int i = 0; i < n; i++)
    {
        double a, b;
        cin >> a >> b;
        v[i].x = a;
        v[i].y = b;

        if(v[i].x < v[leftbottomIdx].x || (v[i].x == v[leftbottomIdx].x && v[i].y < v[leftbottomIdx].y))
            leftbottomIdx = i;
    }

    swap(v[0], v[leftbottomIdx]);
    sort(v + 1, v + n, [](const Point& a, const Point& b) {
        return cross(a - v[0], b - v[0]) >= 0;
    });

    int lst = 2;
    st[0] = v[0];
    st[1] = v[1];
    for(int i = 2; i < n; i++)
    {
        while(lst >= 2 && cross(st[lst - 1] - st[lst - 2], v[i] - st[lst - 1]) <= 0)
            lst--;
        st[lst++] = v[i];
    }

    cout << lst << '\n';
    for(int i = 0; i < lst; i++)
    {
        cout << fixed << setprecision(12) << st[i].x << ' ' << fixed << setprecision(12) << st[i].y << '\n';
    }



    return 0;
}