Cod sursa(job #1411186)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 31 martie 2015 15:16:58
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

#define Point pair<double,double>
#define x first
#define y second

const int Nmax = 120000;

/**
    < 0 for counter-clockwise (trigonometric)
    = 0 for collinear
    > 0 for clockwise (anti-trigonometric)
**/

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

Point points[Nmax];
Point sol[Nmax];

void convexHull(Point points[], int N, Point hull[], int &sizeHull)
{
    int U[Nmax], L[Nmax];
    int dimU = 0, dimL = 0;
    sizeHull = 0;

    for (int i = 0; i < N; ++i)
    {
        while (dimU >= 2 && CCW(points[U[dimU - 2]], points[U[dimU - 1]], points[i]) >= 0)
            dimU--;

        U[dimU++] = i;
    }

    for (int i = N - 1; i >= 0; --i)
    {
        while (dimL >= 2 && CCW(points[L[dimL - 2]], points[L[dimL - 1]], points[i]) >= 0)
            dimL--;

        L[dimL++] = i;
    }

    dimU--;
    dimL--;

    for (int i = 0; i < dimU; ++i)
        hull[sizeHull++] = points[U[i]];

    for (int i = 0; i < dimL; ++i)
        hull[sizeHull++] = points[L[i]];
}

int main()
{
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");

    int N, dim = 0;
    in >> N;

    for (int i = 0; i < N; ++i)
        in >> points[i].x >> points[i].y;

    convexHull(points, N, sol, dim);

    out << dim << "\n";

    for (int i = 0; i < dim; ++i)
    {
        out << fixed << setprecision(10);
        out << sol[i].x << " " << sol[i].y << "\n";
    }

    return 0;
}