Cod sursa(job #2806132)

Utilizator namesurname01Name Surname namesurname01 Data 22 noiembrie 2021 13:22:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#define N 120002
#include <algorithm>
#include <bitset>
#include <iomanip>

using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

bitset <N> viz;
int who[N];
struct bla
{
    long double x, y;
}v[N];
bool cmp(bla A, bla B)
{
    if (A.x != B.x) return A.x < B.x;
    return A.y < B.y;
}

long double det(int a, int b, int c)
{
    long double x1 = v[a].x, x2 = v[b].x, x3 = v[c].x, y1 = v[a].y, y2 = v[b].y, y3 = v[c].y;
    long double d;
    d = (x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x1 * y3 - x2 * y1);
    return d;
}
int main()
{
    int n, nr = 1, i, ss = 2;
    f >> n;
    for (int i = 1;i <= n;++i) f >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1, cmp);
    who[1] = 1;
    who[2] = 2, viz[2] = 1;
    i = 3;
    while (!viz[1])
    {
        while (viz[i])
        {
            if (i == n) nr = -1;
            i += nr;
        }
        while (ss >= 2 && det(who[ss - 1], who[ss], i) < 0)
            viz[who[ss]] = 0, --ss;
        who[++ss] = i;
        viz[who[ss]] = 1;
    }
    g << ss - 1 << '\n';
    for (int i = 2;i <= ss;++i)
    {
        g << fixed << setprecision(15) << v[who[i]].x << ' ';
        g << fixed << setprecision(15) << v[who[i]].y << '\n';
    }
    f.close();
    g.close();
    return 0;
}