Cod sursa(job #3317209)

Utilizator RaduPaunTrifRadu Paun Trif RaduPaunTrif Data 22 octombrie 2025 18:40:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>
using namespace std;

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

#define f first
#define s second

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



int st[MXN + 1];
int vf, vfc;

struct punct {
    double f, s;
    int ord;
};

punct v[MXN + 1];

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

bool peste(punct A, punct B, punct 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()
{
    int n;
    in >> n;
    for(int i = 1; i <= n; ++i)
        in >> v[i].f >> v[i].s;
    sort(v+1, v+n+1, cmp);
    punct a, b;
    a = v[1];
    b = v[n];
    for(int i = 2; i <= n - 1; ++i) {
        if(!peste(a,b,v[i]))
            v[i].ord=1;
        else
            v[i].ord=2;
    }
    st[1]=1;
    vf = 1;
    for(int i = 2; i <= n; ++i) {
        if(v[i].ord == 1 || v[i].ord == 0)
        {
            while(vf > 1 && !peste(v[st[vf - 1]], v[st[vf]],v[i]))
                vf--;
            vf++;
            st[vf]=i;
        }
    }
    vfc = vf;
    st[vfc]=n;
    for(int i = n - 1; i >= 1; --i) {
        if(v[i].ord == 2 || v[i].ord == 0)
        {
            while(vf > vfc && !peste(v[st[vf - 1]], v[st[vf]], v[i]))
                vf--;
            vf++;
            st[vf]=i;
        }
    }
    out << vf - 1 << '\n';
    for(int i = 1; i < vf; ++i)
        out << fixed << setprecision(6) << v[st[i]].f << " " << v[st[i]].s << " " << "\n";

    return 0;
}