Cod sursa(job #3153843)

Utilizator europeanMafiot European european Data 1 octombrie 2023 16:12:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>
using namespace std;

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

#define miauDebug
#ifdef miauDebug
#define mau(x) MIAUMIAU(#x, x)
#else
#define mau(x)
#endif

void MIAUMIAU(const char* var_name, auto var_value) {
    cout << var_name << " = " << var_value << endl;
}

using ll = long long;
const int nM = 5*1e3+5;
const ll MOD = 998244353;
// :3

int n;
struct xy
{
    double x, y;
};

xy v[120005];
xy st[120005];
xy sol[120005];

int vf, lf;

bool cmp(xy a, xy b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

xy jos, sus;

bool semn(xy a, xy b, xy c)
{
    return (a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x) >= 0;
}

void solve() {
    fin >> n;

    for(int z = 1; z <= n; z++)
        fin >> v[z].x >> v[z].y;


    sort(v + 1, v + n + 1,cmp);
    jos = v[1];
    sus = v[n];
    st[++vf] = v[1];
    for (int i = 2; i <= n; ++i)
    {
        while (vf > 1 && !semn(st[vf - 1],st[vf],v[i]))
            --vf;
        st[++vf] = v[i];
    }
    for (int i = 1; i <= vf; ++i)
        sol[i] = st[i];
    lf = vf;
    vf = 0;
    st[++vf] = v[n];
    for (int i = n - 1; i >= 1; --i)
    {
        while (vf > 1 && !semn(st[vf - 1],st[vf],v[i]))
            --vf;
        st[++vf] = v[i];
    }
    for (int i = 2; i <= vf; ++i)
        sol[i + lf - 1] = st[i];
    lf = lf + vf - 2;

    fout << lf << '\n';
    fout << fixed << setprecision(6);
    for(int z = 1; z <= lf; z++)
        fout << sol[z].x << ' ' << sol[z].y << '\n';
}
signed main()
{
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int tt = 1; //cin >> tt;

    while(tt--)
        solve();
}
/*
6
1 536870912
1 268435456
1 134217728
1 4194304
1 256
1 1

*/