Cod sursa(job #3325904)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 26 noiembrie 2025 19:58:33
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct {
    long double x, y;
} pct[120002], stiv[120002];
int n, i, mi, top;
Punct rasp[120002];

static inline long double Det(Punct p1, Punct p2, Punct p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.x - p1.y);
}

static inline bool Cmp(Punct a, Punct b) {
    return Det(pct[1], a, b) > 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n;
    mi = -1;
    for(i = 1; i <= n; i++) {
        fin >> pct[i].x >> pct[i].y;
        if(mi == -1 || pct[i].y < pct[mi].y || (pct[i].y == pct[mi].y && pct[i].x < pct[mi].x)) {
            mi = i;
        }
    }

    swap(pct[1], pct[mi]);
    sort(pct + 2, pct + n + 1, Cmp);

    for(i = 1; i <= n; i++) {
        while(top > 2 && Det(stiv[top], stiv[top - 1], pct[i]) < 0) top--;
        stiv[++top] = pct[i];
    }

    fout << top << "\n";
    for(i = 1; i <= top; i++) fout << setprecision(12) << fixed << pct[i].x << " " << pct[i].y << "\n";

    return 0;
}