Cod sursa(job #2907090)

Utilizator Eraserurares campean Eraseru Data 28 mai 2022 18:12:21
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef pair<double, double> STR;
long double eroare = 1e-12;
STR v[120002];
STR ans[120002];
STR res[120002];
int c, i, n, vf, ok[120002], st[120002];
long double maxim;
long double prod(STR K, STR L, STR M)
{
    return (L.x - K.x) * (M.y - K.y) - (M.x - K.x) * (L.y - K.y);
}
int main()
{
    fin >> n;
    for(i = 1; i <= n; i++)
    {
        fin >> v[i].first >> v[i].second;
        if(v[i].second > maxim) maxim = v[i].second;
    }
    sort(v + 1, v + n + 1);
c = 1;
    vf = 2;
    st[1] = 1;
    st[2] = 2;
    ok[2] = 1;
    int p = 1;
    for(i = 1; i > 0; i += p)
    {
        if(ok[i]) continue;
            while(vf > 1 && prod(v[st[vf - 1]], v[st[vf]], v[i]) < eroare)
                ok[st[vf--]] = 0;
            st[++vf] = i;
            ok[i] = 1;
        if(i == n) p = -1;
    }
  // for(i = 1; i <= vf; i++) cout << v[st[i]].x << ' ' << v[st[i]].y << '\n';
        fout << vf - 1 << '\n';
        for(i = 1; i < vf; i++) ans[i].x = v[st[i]].x, ans[i].y = v[st[i]].y;
        for(i = 1; i < vf; i++) fout << fixed << setprecision(6) << ans[i].x << ' ' << ans[i].y << '\n';
}