Cod sursa(job #3360025)

Utilizator CarenaMironov Cezar Luca Carena Data 7 iulie 2026 18:23:25
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX=12e4+5;
int n;
complex<double> v[NMAX];
vector<complex<double>> env;
stack<complex<double>> st;

bool cmpr(complex<double> p, complex<double> q)
{
    return p.real()<q.real();
}

double ord(complex<double> a, complex<double> b, complex<double> c)
{
    complex<double> p=b-a, q=c-a;
    return p.real()*q.imag()-p.imag()*q.real();
}

void get_envelope(bool b)
{
    int s=b?n:1, sgn=1-2*b;
    complex<double> tp(1e10);
    for(int i=s;sgn*(i-n-1+s)<=0;i+=sgn)
        if(st.empty())
            st.push(v[i]);
        else if(st.size()==1 && tp.real()>2e9)
            tp=v[i];
        else
        {
            while(!st.empty() && ord(v[i], tp, st.top())<=0)
            {
                tp=st.top();
                st.pop();
            }
            st.push(tp);
            tp=v[i];
        }
    
    if(!b)
        st.push(tp);
    while(st.size()>b)
    {
        env.push_back(st.top());
        st.pop();
    }
}

int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
    {
        double a, b;
        in>>a>>b;
        v[i]={a, b};
    }
    sort(v+1, v+n+1, cmpr);
    get_envelope(0);
    get_envelope(1);
    out<<env.size()<<'\n';
    out<<fixed<<setprecision(10);
    for(auto p:env)
        out<<p.real()<<" "<<p.imag()<<'\n';
    return 0;
}