Cod sursa(job #3032923)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 23 martie 2023 09:10:18
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
/// [A][M][C][B][N] ///
#include <bits/stdc++.h>
const char nl = '\n';
const char sp = ' ';
const int mod = 666013;
const int inf = 0x3f3f3f3f;
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int N = 12e4;

struct point {
    long double x, y;
} v[N + 1];

int n;

bool trigorder(const point& a, const point& b, const point& c) {
    return (b.x - a.x) * (c.y - a.y) >= (b.y - a.y) * (c.x - a.x);

}

bool cmp(const point& a, const point& b) {
    return trigorder(v[1], a, b);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fin >> n;
    int foo = 1;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i].x >> v[i].y;
        if (v[foo].x > v[i].x || (v[foo].x == v[i].x && v[foo].y > v[i].y)) {
            foo = i;
        }
    }
    swap(v[foo], v[1]);
    // v[1] - punctul de la care incepem
    sort(v + 2, v + n + 1, cmp);
    vector<int> H{ 1, 2 };
    for (int i = 3; i <= n; ++i) {
        while (!trigorder(v[H[H.size() - 2]], v[H.back()], v[i])) {
            H.pop_back();
        }
        H.push_back(i);
    }
    fout << H.size() << nl;
    for (auto& i : H) {
        fout << fixed << setprecision(6) << v[i].x << sp << v[i].y << nl;
    }
}