Cod sursa(job #2618097)

Utilizator richardbaczur1Baczur Richard richardbaczur1 Data 23 mai 2020 17:24:57
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
#define infile "infasuratoare.in"
#define outfile "infasuratoare.out"
#define x first
#define y second

typedef std::pair<double, double> Point;

const int NMAX = 120005;
const double EPS = 1e-12;

int n, st[NMAX], head;
Point v[NMAX];
std::bitset<NMAX> viz;

double crossProduct(Point O, Point A, Point B)
{
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

void convex_hull()
{
    sort(v + 1, v + n + 1);
    st[1] = 1;
    st[2] = 2;
    head = 2;
    viz[2] = 1;

    for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p)))
    {
        if (viz[i]) continue;
        while (head >= 2 && crossProduct(v[st[head-1]], v[st[head]], v[i]) < EPS)
            viz[st[head--]] = 0;
        st[++head] = i;
        viz[i] = true;
    }

    std::cout << head - 1 << "\n";
    std::cout << std::setprecision(6) << std::fixed;
    for (int i = 1; i < head; ++i)
    {
        std::cout << v[st[i]].x << " " << v[st[i]].y << "\n";
    }
}

int main()
{
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        std::cin >> v[i].x >> v[i].y;
    }
    convex_hull();


    fclose(stdin);
    fclose(stdout);
    return 0;
}