Cod sursa(job #2531532)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 26 ianuarie 2020 13:22:10
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>

using namespace std;

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

typedef pair  < long double, long double > Point;

const int NMAX = 12e4 + 5;

int N;

Point A[NMAX];

int Stack[NMAX], K;
bool Sel[NMAX];

static inline void Read ()
{
    f.tie(NULL);

    f >> N;

    for(int i = 1; i <= N; ++i)
        f >> A[i].first >> A[i].second;

    sort(A + 1, A + N + 1);

    return;
}

static inline long double Det3 (Point A, Point B, Point C)
{
    return (long double)(A.first * B.second + B.first * C.second + C.first * A.second) - (long double)(B.second * C.first + C.second * A.first + A.second * B.first);
}

static inline void Convex_Hull ()
{
    Sel[2] = 1;

    Stack[++K] = 1;
    Stack[++K] = 2;

    for(int i = 3; i <= N; ++i)
    {
        while(K > 1 && Det3(A[Stack[K - 1]], A[Stack[K]], A[i]) >= 0)
        {
            Sel[Stack[K]] = 0;


            --K;
        }

        Sel[i] = 1;

        Stack[++K] = i;
    }

    for(int i = N; i >= 1; --i)
        if(!Sel[i])
        {
            while(K > 1 && Det3(A[Stack[K - 1]], A[Stack[K]], A[i]) >= 0)
            {
                Sel[Stack[K]] = 0;


                --K;
            }

            Sel[i] = 1;

            Stack[++K] = i;
        }

    return;
}

static inline void Write ()
{
    g << (K - 1) << '\n';

    g << setprecision(6) << fixed;

    for(int i = 1; i < K; ++i)
        g << A[Stack[i]].first << ' ' << A[Stack[i]].second << '\n';

    return;
}

int main()
{
    Read();

    Convex_Hull();

    Write();

    return 0;
}