Cod sursa(job #682703)

Utilizator attila3453Geiszt Attila attila3453 Data 19 februarie 2012 13:36:44
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");

const int maxn = 120000;
const int infinit = 1000000000;

float x[maxn], y[maxn];
int init, sol[maxn], ind[maxn];

bool sortfunc(int i, int j)
{
    return (x[i] - x[init]) * (y[j] - y[init]) > (x[j] - x[init]) * (y[i] - y[init]);
}

bool right(int i, int j, int k)
{
    return (x[i] * (y[j] - y[k]) + x[j] * (y[k] - y[i]) + x[k] * (y[i] - y[j])) > 0;
}

int main()
{
    int i, n, l = 0, p = 0;

    fi>>n;

    init = 0;

    x[0] = y[0] = infinit;

    for(i = 1; i <= n; i++)
    {
        fi>>x[i]>>y[i];
        if(x[i] < x[init] || (x[i] == x[init] && y[i] < y[init]))
            init = i;
    }

    for(i = 1; i <= n; i++)
        if(i != init) ind[++l] = i;

    sort(ind + 1, ind + n, sortfunc);

    p = 1;
    sol[1] = init;
    for(i = 1; i < n; i++)
    {
        while(p >= 2 && !right(sol[p-1], sol[p], ind[i]))
            p--;
        sol[++p] = ind[i];
    }

    fo<<p<<'\n';
    for(i = 1; i <= p; i++)
        fo<<x[sol[i]]<<' '<<y[sol[i]]<<'\n';

    return 0;
}