Cod sursa(job #1006055)

Utilizator pulseOvidiu Giorgi pulse Data 6 octombrie 2013 11:16:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

typedef pair <double, double> point;

const int INF=120005;

int n,head;
point v[INF],stack[INF];

void read ()
{
    fin>>n;
    for (int i=1; i<=n; i++)
        fin>>v[i].x>>v[i].y;
}

inline double product (point A, point B, point C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

inline int compare (point p1, point p2)
{
    return product (v[1],p1,p2)<0;
}

void sort_points ()
{
    int k=1;

    for (int i=2; i<=n; i++)
    {
        if (v[i].x<v[k].x)
        {
            k=i;
        }
        else if (v[i].x==v[k].x)
        {
            if (v[i].y<v[k].y)
            {
                k=i;
            }
        }
    }
    swap (v[1],v[k]);
    sort (v+2, v+n+1, compare);
}

void convex_hull ()
{
    sort_points ();

    stack[1]=v[1];
    stack[2]=v[2];

    head=2;
    for (int i=3; i<=n; i++)
    {
        while (head>=2 && product(stack[head-1],stack[head],v[i])>0)
            --head;
        stack[++head]=v[i];
    }

}

void print ()
{
    fout<<fixed;
    fout<<head<<"\n";
    for (int i=head; i>=1; i--)
    {
        fout<<setprecision(9)<<stack[i].x<<" "<<stack[i].y<<"\n";
    }
}

int main ()
{
    read ();
    convex_hull ();
    print ();
}