Cod sursa(job #1686555)

Utilizator ZenusTudor Costin Razvan Zenus Data 12 aprilie 2016 12:15:13
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 120009;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int i;
bool compare(point , point);

class ConvexHull
{
    public :
    point v[nmax] , ch[nmax];
    int n , S;

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

        return a * C.x + b * C.y + c;
    }

    void work()
    {
        int i;

        for (i = 2 ; i <= n ; ++i)
        if (v[i] < v[1]) swap(v[i] , v[1]);

        sort(v + 2 , v + n + 1 , compare);

        S = 0;
        ch[++S] = v[S];
        ch[++S] = v[S];

        for (i = 3 ; i <= n ; ++i)
        {
            while (2 <= S && cross(ch[S - 1] , ch[S] , v[i]) > 0) S--;
            ch[++S] = v[i];
        }
    }
} solve;

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

int main()
{

fin >> solve.n;

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

solve.work();

fout << solve.S << '\n';

for (i = 1 ; i <= solve.S ; ++i)
{
    fout << fixed << setprecision(9) << solve.ch[i].x << " ";
    fout << fixed << setprecision(9) << solve.ch[i].y << '\n';
}


return 0;
}