Cod sursa(job #2907041)

Utilizator Eraserurares campean Eraseru Data 28 mai 2022 15:59:27
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 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);
}
bool cmp(STR A, STR B)
{
    if(A.y != maxim)
    {
        if(A.y > B.y) return false;
        return true;
    }
    else
    {
        if(A.y < B.y) return false;
        return true;
    }
}
int main()
{
    cin >> n;
    for(i = 1; i <= n; i++)
    {
        cin >> 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;
    for(i = 1, p = 1; i > 0; i += (p = (i == n ? -p : 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;
    }
  // for(i = 1; i <= vf; i++) cout << v[st[i]].x << ' ' << v[st[i]].y << '\n';
   if(c == 1)
   {
        cout << 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++) cout << fixed << setprecision(6) << ans[i].x << ' ' << ans[i].y << '\n';
   }
   if(c == 2)
   {

   }
}