Cod sursa(job #3154876)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 6 octombrie 2023 17:54:00
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
struct point {
    double x, y;
};
point v[120005], st[120005];

double angle(point a, point b, point c) {
    return (b.y - a.y) * (c.x - a.x) - (b.x - a.x) * (c.y - a.y);
}

bool cmp(point a, point b) {
    return angle(v[1], a, b) > 0;
}

int top;

int main()
{
    in >> n;

    int pos = 0;

    for (int i = 1; i <= n; i++) {
        in >> v[i].x >> v[i].y;
        if (pos == 0 || (v[i].x < v[pos].x || (v[i].x == v[pos].x && v[i].y < v[pos].y))) {
            pos = i;
        }
    }

    swap(v[1], v[pos]);
    sort(v + 2, v + n + 1, cmp);

    top = 2;
    st[1] = v[1];
    st[2] = v[2];

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

    out << top << '\n';
    for (int i = top; i > 0; i--)
        out << fixed << setprecision(6) << st[i].x << " " << st[i].y << '\n';
    return 0;
}