Cod sursa(job #3338230)

Utilizator mariusharabariMarius Harabari mariusharabari Data 1 februarie 2026 18:41:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int NMAX=12e4+1;

int n;
pair <double, double> v[NMAX];
vector <int> sus, jos;
vector <pair <double, double>> rez;

double aria(pair <double, double> x, pair <double, double> y, pair <double, double> z){
    return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}

int main(){
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i].first>>v[i].second;
    sort(v+1, v+1+n);

    for(int i=1;i<=n;i++){
        while(jos.size()>1&&aria(v[jos[jos.size()-2]], v[jos[jos.size()-1]], v[i])<=0)
            jos.pop_back();
        while(sus.size()>1&&aria(v[sus[sus.size()-2]], v[sus[sus.size()-1]], v[i])>=0)
            sus.pop_back();
        jos.push_back(i);
        sus.push_back(i);
    }

    for(int a:jos)
        rez.push_back(v[a]);

    sus.pop_back();
    reverse(sus.begin(), sus.end());
    sus.pop_back();

    for(int a:sus)
        rez.push_back(v[a]);

    fout<<rez.size()<<'\n';
    fout<<fixed<<setprecision(6);
    for(auto a:rez){
        fout<<a.first<<' '<<a.second<<'\n';
    }
    return 0;
}