Cod sursa(job #883396)

Utilizator Coman95coman cosmin Coman95 Data 19 februarie 2013 23:30:24
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;

#define NMAX 120001

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

int n;
double x[NMAX], y[NMAX];
int ind[NMAX], s[NMAX];
int ip;

bool cmp( int i, int j )
{
    return ( x[i] - x[ip] ) * ( y[j] - y[ip] ) < ( x[j] - x[ip] ) * ( y[i] - y[ip]);
}
bool ok( int x, int y, int k );

int main()
{
    fin >> n;
    fin >> x[0] >> y[0];
    for( int i = 1; i < n; ++i )
    {
        fin >> x[i] >> y[i];
        if( x[i] < x[ip] || ( x[i] == x[ip] && y[i] < y[ip] ) )
            ip = i;
    }
    for( int i = 0; i < n; ++i )
        ind[i] = i;
    ind[ip] = ind[n-1];
    sort( ind, ind+n-1, cmp );
    int poz = 2;
    s[0] = ip;
    s[1] = ind[0];
    for( int i = 1; i < n - 1; ++i )
    {
        while( poz >= 2 && ( !ok(s[poz - 2], s[poz - 1], ind[i] ) ) )
            poz--;
        s[poz++] = ind[i];
    }
    fout << poz << '\n';
    for( int i = poz - 1; i >= 0; --i )
        fout << setprecision(7) << x[s[i]] << ' ' << setprecision(7) << y[s[i]] << '\n';
    fin.close();
    fout.close();
    return 0;
}

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