Cod sursa(job #2289285)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 24 noiembrie 2018 12:42:38
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define x first
#define y second
typedef pair < double, double > PUNCT;

const int MAXN = 120000 + 16;
const double EPS = 1e-12;

int N;
PUNCT Puncte[MAXN];
bool EsteInStiva[MAXN];
int Stiva[MAXN], varf;

void citire();
void afisare();
bool cmpPunct(PUNCT, PUNCT);
double Sarrus(PUNCT, PUNCT, PUNCT);

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

    varf = 1;
    Stiva[1] = 1;

    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]) < EPS)
                EsteInStiva[Stiva[varf--]] = false;
            Stiva[++varf] = i;
            EsteInStiva[i] = true;
        }
    }

    afisare();

    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 - P3.x) * (P2.y - P3.y) - (P2.x - P3.x) * (P1.y - P3.y);
}

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

void citire()
{
    freopen("infasuratoare.in", "r", stdin);
    /// Citim N si coordonatele punctelor
    scanf("%i", &N);
    for(int i = 1; i <= N; ++i)
        scanf("%lf %lf", &Puncte[i].x, &Puncte[i].y);
    fclose(stdin);
}

void afisare()
{
    freopen("infasuratoare.out", "w", stdout);
    /// Afisam solutia
    printf("%i\n", varf - 1);
    for(int i = 1; i < varf; ++i)
        printf("%.6lf %.6lf\n", Puncte[Stiva[i]].x, Puncte[Stiva[i]].y);
    fclose(stdout);
}