Cod sursa(job #999808)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 21 septembrie 2013 15:01:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
#include <fstream>
#include <utility>
#include <cstdlib>
#include <ctime>
#include <iomanip>

struct Point
{
    double x, y;
    Point() : x(), y() {}
    Point(double a, double b) : x(a), y(b) {}
};

double ccw(Point a, Point b, Point c);
int comp(Point a, Point b, Point c);
void quick(Point *A, int left, int right);
void sorts(Point *A, int nV);
int convex(Point *A, Point *B, int nA);

int main()
{
    srand(time(NULL));
    std::ifstream in("infasuratoare.in");
    std::ofstream out("infasuratoare.out");
    int nV;
    double a, b;
    in >> nV;
    Point *Arr = new Point[nV + 1], *cH = new Point[nV + 1];;
    for(int i = 1; i <= nV; i++)
    {
        in >> a >> b;
        Arr[i] = Point(a, b);
    }
    int nC = convex(Arr, cH, nV);
    out << nC << '\n';
    out << std::fixed;
    for(int i = nC; i >= 1; i--)
        out << std::setprecision(9) << cH[i].x << ' ' << cH[i].y << '\n';
    return 0;
}

int convex(Point *A, Point *B, int nA)
{
    sorts(A, nA);
    B[1] = A[1];
    B[2] = A[2];
    int nB = 2;
    for(int i = 3; i <= nA; i++)
    {
        while(nB >= 2 && ccw(B[nB - 1], B[nB], A[i]) > 0)
            nB--;
        B[++nB] = A[i];
    }
    return nB;
}

double ccw(Point a, Point b, Point c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int comp(Point a, Point b, Point c)
{
    return ccw(a, b, c) < 0;
}

void quick(Point *A, int left, int right)
{
    if(left >= right) return;
    Point pivot = A[left + rand() % (right - left)];
    int l = left, r = right;
    while(l < r)
    {
        while(comp(A[1], A[l], pivot))
            l++;
        while(comp(A[1], pivot, A[r]))
            r--;
        if(l <= r)
        {
            std::swap(A[l], A[r]);
            l++;
            r--;
        }
    }
    quick(A, left, r);
    quick(A, l, right);
}

void sorts(Point *A, int nV)
{
    int p = 1;
    for(int i = 2; i <= nV; i++)
        if(A[p].y > A[i].y)
            p = i;
        else if(A[p].y == A[i].y && A[p].x > A[i].x)
            p = i;
    std::swap(A[p], A[1]);
    quick(A, 2, nV);
}