Cod sursa(job #822982)

Utilizator razvan.popaPopa Razvan razvan.popa Data 24 noiembrie 2012 13:15:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<fstream>
#include<algorithm>
#include <iomanip>
#define nMax 120000
#define x first
#define y second
using namespace std;

typedef pair < double, double > punct;

punct P[nMax], S[nMax];

int dimS;

int N;


void read(){
    ifstream fin("infasuratoare.in");

    fin >> N;

    for(int i=0; i<N; ++i){
        fin >> P[i].x >> P[i].y;

        if(P[i] < P[0])
           swap(P[0], P[i]);
    }

    fin.close();
}

inline double crossProduct(const punct &a, const punct &b, const punct &c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool mycmp(const punct &a, const punct &b){
    return crossProduct(P[0], a, b) > 0;
}

void solve(){
    sort(P+1, P+N, mycmp);

    S[++dimS] = P[0];
    S[++dimS] = P[1];

    for(int i=2; i<N; ++i){
        while(dimS >= 1 && crossProduct(S[dimS - 1], S[dimS], P[i]) < 0)
            dimS --;

        S[++dimS] = P[i];
    }
}

void print(){
    ofstream fout("infasuratoare.out");

    fout << fixed << dimS << '\n';

    for(int i=1; i<=dimS; ++i)
       fout << setprecision(9) << S[i].x << " " << S[i].y << '\n';

    fout.close();
}

int main(){
    read();
    solve();
    print();

    return 0;
}