Cod sursa(job #3315851)

Utilizator burcuriciBucur Stefan burcurici Data 16 octombrie 2025 11:41:17
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef long double ld;

int n;
pair<ld,ld> v[120005];
stack<pair<ld,ld>> s, a, b;

void citire()
{
    fin>>n;
    for(int i=0; i<n; i++){
        pair<ld,ld> p;
        fin>>p.first>>p.second;
        v[i] = p;
    }
}

bool cmp(pair<ld,ld> a, pair<ld,ld> b)
{
    if(a.first == b.first) return a.second<b.second;
    return a.first<b.first;
}

void parc1(int i, int j, pair<ld,ld> q)
{
    if(i>=j) return;
    if(s.top() == q){
        s.push(v[i]);
        parc1(i+1,j,q);
    }
    else{
        pair<ld,ld> aux = s.top();
        s.pop();
        ld D = (s.top().first*aux.second + aux.first*v[i].second + v[i].first*s.top().second);
        D -= (v[i].first*aux.second + aux.first*s.top().second + s.top().first*v[i].second);

        if(D>0){
            s.push(aux);
            s.push(v[i]);
            parc1(i+1,j,q);
        }
        else parc1(i,j,q);
    }
}

void parc2(int i, int j, pair<ld,ld> q)
{
    if(i<=j) return;
    if(s.top() == q){
        s.push(v[i]);
        parc2(i-1,j,q);
    }
    else{
        pair<ld,ld> aux = s.top();
        s.pop();
        ld D = (s.top().first*aux.second + aux.first*v[i].second + v[i].first*s.top().second);
        D -= (v[i].first*aux.second + aux.first*s.top().second + s.top().first*v[i].second);

        if(D>0){
            s.push(aux);
            s.push(v[i]);
            parc2(i-1,j,q);
        }
        else parc2(i,j,q);
    }
}

void afisare()
{
    while(!s.empty()){
        b.push(s.top());
        s.pop();
    }

    fout<<b.size()<<"\n";
    while(!b.empty()){
        fout<<b.top().first<<" "<<b.top().second<<"\n";
        b.pop();
    }
}

int main()
{
    citire();

    sort(v,v+n,cmp);

    s.push(v[0]);
    parc1(1,n,s.top());
    parc2(n-2,0,s.top());

    afisare();
}