Cod sursa(job #900332)

Utilizator Mitza444Vidrean Mihai Mitza444 Data 28 februarie 2013 19:08:54
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
#define MAX 120003
#define PP pair<double,double>
#define x first
#define y second
PP v[MAX];
int S[MAX],n;
double cross_product(PP v1,PP v2,PP v3){
    return (v2.x-v1.x)*(v3.y-v1.y)-(v2.y-v1.y)*(v3.x-v1.x);
}
int comp(PP v1,PP v2){
    return cross_product(v[1],v1,v2) < 0;
}
int main(){
    int i,pymin=1;
    PP top;
    ifstream f("infasuratoare.in");
    f>>n;
    for(i=1;i<=n;++i){
        f>>v[i].x>>v[i].y;
        if(v[i]<v[pymin])
            pymin=i;
    }
    f.close();
    swap(v[1],v[pymin]);
    sort(v+2,v+n+1,comp);
    S[++S[0]]=1;S[++S[0]]=2;
    for(i=3;i<=n;++i){
        while(cross_product(v[S[S[0]-1]],v[S[S[0]]],v[i])>0 && S[0]>=2)
            --S[0];
        S[++S[0]]=i;
    }
    ofstream g("infasuratoare.out");
    g<<fixed<<S[0]<<"\n";
    for(i=S[0];i;--i)
        g<<setprecision(6)<<v[S[i]].x<<" "<<v[S[i]].y<<"\n";
    g.close();
    return 0;
}