Cod sursa(job #2289260)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 24 noiembrie 2018 12:25:36
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 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 Puncte[MAXN];
bool EsteInStiva[MAXN];
int Stiva[MAXN], varf;
int N;

bool cmpPunct(PUNCT, PUNCT);
double Sarrus(PUNCT, PUNCT, PUNCT);

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", &Puncte[i].x, &Puncte[i].y);

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

    varf = 1;
    Stiva[1] = 1;
    EsteInStiva[1] = true;

    for(int i = 1, p = 1; i > 0; i += p = (i == N ? -p : p))
    {
        if(!EsteInStiva[i])
        {
            /// Vrem sa adaugam i in infasuratoare, asa ca vom elimina toate punctele
            /// precedente ce formeaza o concavitate
            while(varf >= 2 && Sarrus(Puncte[Stiva[varf - 1]], Puncte[Stiva[varf]], Puncte[i]) < 0)
                EsteInStiva[Stiva[varf--]] = false;
            Stiva[++varf] = i;
            EsteInStiva[i] = true;
        }
    }

    /// Afisam solutia
    printf("%i\n", varf);
    for(int i = 1; i <= varf; ++i)
        printf("%.6lf %.6lf\n", Puncte[Stiva[i]].x, Puncte[Stiva[i]].y);

    return 0;
}

/**
    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;
}

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