Cod sursa(job #1124317)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 26 februarie 2014 12:04:47
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

typedef pair<double,double> pdd;
#define M 120005
int N;
pdd V[M];
const double EPS = 1e-12;
int S[M],H;
bool us[M];

double cp( pdd O, pdd A, pdd B ){
    return  (A.first - O.first)*(B.second-O.second) - (  B.first - O.first  )*( A.second - O.second )   ;
}

int main()
{
    ifstream f("infasuratoare.in");
    f>>N;
    for(register int i=1;i<=N;++i)
        f>>V[i].first>>V[i].second;
    f.close();
    sort( V+1, V+N+1 );
    S[1]=1; S[2]=2; H=2;
    us[2]=true;
    int p=1;
    for(register int i=1,p=1;i>0; i += (p = (i == N ? -p : p))){
        if( us[i] ) continue;
        while( H >= 2 &&  cp( V[ S[H-1] ],V[ S[H] ],V[i] ) < EPS   )
            us[ S[ H-- ] ] = false;
        S[ ++H ] = i;
        us[ i ] = true;
    }
    ofstream g("infasuratoare.out");
    g<<H-1<<'\n';
    g << setprecision(6) << fixed;
    for(register int i=1;i<H;++i){
        g<<V[ S[i] ].first<<" "<<V[ S[i] ].second<<'\n';    }
    return 0;
}