Cod sursa(job #1414050)

Utilizator ZenusTudor Costin Razvan Zenus Data 2 aprilie 2015 12:11:34
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <stack>

using namespace std;

#define NMAX 120007
#define point pair < double , double >
#define x first
#define y second

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

point p[NMAX];
stack < point > inStack;
int i,N;

double cross(point A,point B,point C)
{
    double a = A.y - B.y;
    double b = B.x - A.x;
    double c = A.x * B.y - B.x * A.y;

    double product = a * C.x + b * C.y + c;

    return product;
}

bool compare(point A,point B)
{
    return ( cross(p[1],A,B) < 0);
}

void read()
{
    f >> N;

    for (i=1;i<=N;++i)
    {
        f >> p[i].x >> p[i].y;
        if (p[i] < p[1]) swap(p[1],p[i]);
    }

    sort(p+2,p+N+1,compare);
}

void convexHull()
{
    inStack.push(p[1]);
    inStack.push(p[2]);

    for (i=3;i<=N;++i)
    {
        while (inStack.size() >= 2)
        {
            point prv = inStack.top();
            inStack.pop();

            point prvv = inStack.top();

            if (cross(prvv , prv , p[i]) > 0) continue;
            else
            {
                inStack.push(prv);
                break;
            }
        }

        inStack.push(p[i]);
    }
}

void writeConvexHull()
{
    g << inStack.size() << '\n';

    while (inStack.size())
    {
        g << fixed << setprecision(13);
        g << inStack.top().first << " ";

        g << fixed << setprecision(13);
        g << inStack.top().second << '\n';

        inStack.pop();
    }
}

int main()
{

read();
convexHull();
writeConvexHull();

return 0;
}