Cod sursa(job #3315954)

Utilizator RaduPaunTrifRadu Paun Trif RaduPaunTrif Data 16 octombrie 2025 16:49:35
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

const int MXN = 120000;
const int BRD = 1e9;

int n;
double x, y;
pair<double, double> v[MXN + 1],
                     sus[MXN + 1],
                     jos[MXN + 1];
int vf, vf1, vf2;

bool cmp(pair<double, double> A, pair<double, double> B) {
    if(A.f != B.f)
        return A.f < B.f;
    else
        return A.s < B.s;
}

bool peste(pair<double, double> A, pair<double, double> B, pair<double, double> C) {
    // "+" -> peste
    // "-" -> sub
    return (A.f * B.s + B.f * C.s + C.f * A.s > C.f * B.s + A.f * C.s + B.f * A.s);
}

int main()
{
    cin >> n;
    vf = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> x >> y;
        //x += BRD, y += BRD;
        v[++vf].f = x, v[vf].s = y;
    }
    sort(v + 1, v + 1 + n);
    pair <double, double> a1 = v[1], a2 = v[n];
    vf1 = vf2 = 0;
    for(int i = 2; i < n; ++i) {
        if(peste(a1, a2, v[i]))
            sus[++vf1] = v[i];
        else
            jos[++vf2] = v[i];
    }
    stack <int> st;
    st.push(1), st.push(2);
    pair <double, double> p1, p2;
    int u1, u2;
    for(int i = 3; i <= vf1; ++i) {
        u2 = st.top(), st.pop();
        u1 = st.top(), st.push(u2);
        p1 = v[u1], p2 = v[u2];
        cout << p1.f << ' ' << p1.s << '\n';
        cout << p2.f << ' ' << p2.s << '\n';
        if(peste(p1, p2, sus[i]))
            st.push(i);
        else
            st.pop(), st.push(i);
    }
    cout << '\n';
    int sz1, sz2;
    sz1 = st.size();
    while(!st.empty())
        st.pop();
    st.push(1), st.push(2);
    for(int i = 3; i <= vf2; ++i) {
        u2 = st.top(), st.pop();
        u1 = st.top(), st.push(u2);
        p1 = v[u1], p2 = v[u2];
        cout << p1.f << ' ' << p1.s << '\n';
        cout << p2.f << ' ' << p2.s << '\n';
        if(!peste(p1, p2, sus[i]))
            st.push(i);
        else
            st.pop(), st.push(i);
    }
    sz2 = st.size();
    return 0;
}