Cod sursa(job #3318088)

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

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

int n, im;
deque<pct> S;

void citire()
{
    int xm=1e9, ym=1e9;

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

        if(V[i].y < ym || (V[i].y == ym && V[i].x < xm)){
            ym = V[i].y;
            xm = V[i].x;
            im = i;
        }
    }
}

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

bool cmp(pct a, pct b)
{
    long double d = D(V[0],a,b);
    if(d > 0) return 1;
    if(d == 0 && abs(a.x) < abs(b.x) && a.x>=V[0].x && b.x>=V[0].x) return 1;
    if(d == 0 && abs(a.x) > abs(b.x) && a.x<V[0].x && b.x<V[0].x) return 1;
    return 0;
}

void parc(int i)
{
    if(i==n-1){
        S.push_back(V[i]);
        return;
    }
    if(S.size()==2){
        S.push_back(V[i]);
        parc(i+1);
    }
    else{
        pct k, l, m;
        l = S.back(); S.pop_back();
        k = S.back();
        m = V[i];
        if(D(k,l,m) >= 0){
            S.push_back(l);
            S.push_back(m);
            parc(i+1);
        }
        else parc(i);
    }
    return;
}

int main()
{
    citire();
    swap(V[0],V[im]);
    sort(V+1, V+n, cmp);

    S.push_back(V[0]);
    S.push_back(V[1]);
    parc(2);

    fout<<S.size()<<"\n";
    while(!S.empty()){
        fout<<S.front().x<<" "<<S.front().y<<"\n";
        S.pop_front();
    }
}