Cod sursa(job #3314982)

Utilizator burcuriciBucur Stefan burcurici Data 11 octombrie 2025 18:09:37
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n;
vector<pair<long double,long double>> v;
stack<pair<long double,long double>> S;

void citire()
{
    fin>>n;
    pair<long double,long double> P;
    for(int i=0; i<n; i++){
        fin>>P.first>>P.second;
        v.push_back(P);
    }
}

void qvick(int st, int dr)
{
    if(st>=dr) return;
    int m = (st+dr)/2;
    pair<long double,long double> aux = v[st];
    v[st] = v[m];
    v[m] = aux;

    int i=st, j=dr, d=0;
    while(i<j){
        if(v[i].first>v[j].first){
            auto aux = v[i];
            v[i] = v[j];
            v[j] = aux;
            d = 1-d;
        }
        else if(v[i].first==v[j].first && v[i].second>v[j].second){
            auto aux = v[i];
            v[i] = v[j];
            v[j] = aux;
            d = 1-d;
        }
        i += d;
        j -= 1-d;
    }
    qvick(st,i-1);
    qvick(i+1,dr);
}

void parc(int i, int d, pair<long double,long double> q)
{
    if((i>=n && d==1)||(i<=-1 && d==-1)) return;
    if(S.top() == q){
        S.push(v[i]);
        parc(i+d,d,q);
    }
    else{
        auto aux = S.top();
        S.pop();
        long double det = (S.top().first*aux.second + aux.first*v[i].second + v[i].first*S.top().second);
        det -= (v[i].first*aux.second + aux.first*S.top().second + S.top().first*v[i].second);

        if(det<0){
            S.push(aux);
            S.push(v[i]);
            parc(i+d,d,q);
        }
        else parc(i,d,q);
    }
}

int main()
{
    citire();
    qvick(0,n-1);
    S.push(v[0]);
    pair<long double,long double> q;

    q = v[0];
    parc(1,1,q);
    q = S.top();
    parc(n-2,-1,q);

    fout<<S.size()-1<<'\n';
    while(S.size()>1){
        fout<<S.top().first<<' '<<S.top().second<<'\n';
        S.pop();
    }
}