Cod sursa(job #2510229)

Utilizator Briana_NeaguNeagu Briana Briana_Neagu Data 16 decembrie 2019 08:06:16
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nmax = 120005;

bool fv[nmax];
int down[nmax];
int up[nmax];

struct coord
{
    double x, y;
}punct[nmax];

double det(coord a, coord b, coord c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int main()
{
    int n;
    f >> n;
    for (int i = 1; i <= n; ++ i)
    {
        double x, y;
        f >> x >> y;
        punct[i] = {x, y};
    }
    sort(punct + 1, punct + 1 + n, [](const coord a, const coord b) -> bool{
        if (a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    });

    int lvl1 = 0;
    for (int i = 1; i <= n; ++ i)
    {
        while (lvl1 >= 2 &&  det(punct[i], punct[down[lvl1 - 1]], punct[down[lvl1]]) > 0)
            fv[down[lvl1 --]] = false;
        down[++ lvl1] = i;
        fv[i] = true;
    }
    fv[1] = fv[n] = false;
    int lvl2 = 0;
    for (int i = n; i >= 1; -- i)
    {
        if (fv[i])
            continue;
        while (lvl2 >= 2 && det(punct[i], punct[up[lvl2 - 1]], punct[up[lvl2]]) > 0)
           lvl2 --;
        up[++ lvl2] = i;
    }
    g << lvl1 + lvl2 - 2 << '\n';
    for (int i = lvl1 - 1; i > 1; -- i)
        g << fixed << setprecision(12) << punct[down[i]].x << " " << punct[down[i]].y << '\n';

    for (int i = lvl2; i >= 1; -- i)
        g << fixed << setprecision(12) << punct[up[i]].x << " " << punct[up[i]].y << '\n';
}