Cod sursa(job #1536767)

Utilizator RaileanuCristian Raileanu Raileanu Data 26 noiembrie 2015 17:25:24
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream f2("infasuratoare.out");

#define NMAX 120120

struct Punct
{
    double x, y;

};

bool operator<(Punct p1, Punct p2)
{
    return p1.x < p2.x;
}

double delta(Punct p, Punct q, Punct r)
{
    return (q.x - p.x) * (r.y - p.y) - (r.x - p.x)*(q.y - p.y);
}

int n, kSt;
Punct p[NMAX], st[NMAX];

int main()
{
    int i;

    f >> n;

    for (i=1; i<=n; i++)
        f >> p[i].x >> p[i].y;

        // graham's scan (Andrew )

    sort(p+1, p+n+1);

    st[++kSt]= p[1];
    st[++kSt]= p[2];

    for (i=3; i<=n; i++)
    {
        while ( delta(st[kSt-1], st[kSt], p[i]) < 0 && kSt > 1 )
            kSt--;

        st[++kSt]= p[i];
    }

    st[++kSt]= p[n-1];

    for (i=n-2; i>=1; i--)
    {
        while ( delta(st[kSt-1], st[kSt], p[i]) < 0 && kSt > 1 )
            kSt--;

        st[++kSt]= p[i];
    }

    kSt--;
        // output

    f2.precision(6);
    f2.setf( ios::fixed, ios::floatfield );

    f2 << kSt << "\n";

    for (i=1; i<= kSt; i++)
        f2 << st[i].x << " " << st[i].y << "\n";

    f2.close();
    return 0;
}