Cod sursa(job #2289165)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 24 noiembrie 2018 11:44:48
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.27 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define x first
#define y second
typedef pair < double, double > PUNCT;
const int MAXN = 120000 + 16;

PUNCT InfCon[MAXN], Above[MAXN], Below[MAXN];
int N, AboveN, BelowN;

bool cmpPunct(PUNCT X, PUNCT Y)
{
    if(X.second == Y.second)
        return X.first < Y.first;
    return X.second < Y.second;
}

double Sarrus(PUNCT, PUNCT, PUNCT);
void DivideMiddle();
void BuildAbove();
void BuildBelow();
void PutTogether();

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    /// Citim N si coordonatele punctelor
    scanf("%i", &N);
    for(int i = 1; i <= N; ++i)
        scanf("%lf %lf", &InfCon[i].x, &InfCon[i].y);

    /// Sortam punctele dupa Y si, in caz de egalitate, dupa X
    sort(InfCon + 1, InfCon + N + 1, cmpPunct);

    /** Luam doua puncte care suntem siguri ca se afla in infasuratoarea convexa
        si impartim multimea punctelor in doua:
        Above - punctele ce se afla deasupra (in stanga) vectorului format de cele 2 puncte
        Below - punctele ce se afla dedesubt (in dreapta) **/
    DivideMiddle();
    /// Eliminam din ambele multimi punctele ce ar forma o concavitate
    BuildAbove();
    BuildBelow();
    /// Aducem impreuna punctele ramase intr-un vector (ordine trigonometrica)
    PutTogether();

    printf("%i\n", N);

    for(int i = 1; i <= N; ++i)
        printf("%.6lf %.6lf\n", InfCon[i].x, InfCon[i].y);

    return 0;
}

void PutTogether()
{
    N = 0;
    for(int i = 1; i <= BelowN; ++i)
        InfCon[++N] = Below[i];
    for(int i = AboveN - 1; i > 1; --i)
        InfCon[++N] = Above[i];
}

void BuildBelow()
{
    bool Change;
    do
    {
        Change = false;

        int i = 2;
        while(i < BelowN)
        {
            if(Sarrus(Below[i-1], Below[i+1], Below[i]) < 0)
                i++;
            else
            {
                Change = true;
                for(int j = i; j < BelowN; ++j)
                    Below[j] = Below[j+1];
                BelowN--;
            }
        }

    } while(Change);
}

void BuildAbove()
{
    bool Change;
    do
    {
        Change = false;

        int i = 2;
        while(i < AboveN)
        {
            if(Sarrus(Above[i-1], Above[i+1], Above[i]) > 0)
                i++;
            else
            {
                Change = true;
                for(int j = i; j < AboveN; ++j)
                    Above[j] = Above[j+1];
                AboveN--;
            }
        }

    } while(Change);
}

void DivideMiddle()
{
    AboveN = BelowN = 1;
    Above[1] = Below[1] = InfCon[1];
    for(int i = 2; i < N; ++i)
        if(Sarrus(InfCon[1], InfCon[i], InfCon[N]) < 0)
            Above[++AboveN] = InfCon[i];
        else
            Below[++BelowN] = InfCon[i];
    Above[++AboveN] = Below[++BelowN] = InfCon[N];
}

/**
    Numar positiv -> Punct 3 se afla in stanga vectorului P1P2
    Numar negativ -> Punct 3 se afla in dreapta vectorului P1P2
    | P1.x P1.y 1 |
    | P2.x P2.y 1 |
    | P3.x P3.y 1 |
**/
double Sarrus(PUNCT P1, PUNCT P2, PUNCT P3)
{
    return P1.x * P2.y + P2.x * P3.y + P3.x * P1.y
          -P3.x * P2.y - P2.x * P1.y - P1.x * P3.y;
}