Cod sursa(job #3318712)

Utilizator burcuriciBucur Stefan burcurici Data 28 octombrie 2025 15:07:56
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n;

struct pct{
    long double x, y;
} V[120005];

long double D(pct a, pct b, pct c){
    return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}

bool cmp(pct a, pct b){
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

void citire(){
    fin>>n;
    for (int i = 0; i < n; i++)
        fin>>V[i].x>>V[i].y;
}

int main()
{
    citire();
    sort(V, V + n, cmp);

    vector<pct> S;

    for (int i = 0; i < n; i++) {
        while (S.size() >= 2 && D(S[S.size()-2], S.back(), V[i]) <= 0)
            S.pop_back();
        S.push_back(V[i]);
    }

    int t = S.size() + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (S.size() >= t && D(S[S.size()-2], S.back(), V[i]) <= 0)
            S.pop_back();
        S.push_back(V[i]);
    }

    S.pop_back();

    fout<<S.size()<<"\n"<<fixed<<setprecision(6);
    for (auto &p : S)
        fout<<p.x<<" "<<p.y<<"\n";
}