Cod sursa(job #2052072)

Utilizator DawlauAndrei Blahovici Dawlau Data 29 octombrie 2017 22:37:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct coords{
    double x,y;
};
const int NMAX=120000;
coords v[NMAX],s[NMAX];
int n,k;
void read_data(){
    int i;
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>v[i].x>>v[i].y;
}
bool compare(const coords &P1,const coords &P2){
    if(P1.x<P2.x)
        return true;
    if(P1.x==P2.x)
        if(P1.y<P2.y)
            return true;
    return false;
}
int cross_product(const coords &P1,const coords &P2,const coords &P3){
    return (P1.y-P3.y)*(P1.x-P2.x)-(P1.y-P2.y)*(P1.x-P3.x);
}
bool cmp(const coords &P1,const coords &P2){
    return cross_product(v[1],P1,P2)<0;
}
void sort_data(){
    int i,pos=1;
    for(i=2;i<=n;++i)
        if(compare(v[i],v[pos]))
            pos=i;
    swap(v[pos],v[1]);
    sort(v+2,v+1+n,cmp);
}
void convex_hull(){
    int i;
    s[1]=v[1];
    s[2]=v[2];
    k=2;
    for(i=3;i<=n;++i){
        while(k>=2 and cross_product(s[k],s[k-1],v[i])<0)
            --k;
        s[++k]=v[i];
    }
}
void print(){
    int i;
    for(i=k;i>=1;--i)
        fout<<fixed<<setprecision(9)<<s[i].x<<' '<<s[i].y<<'\n';
}
int main(){
    read_data();
    sort_data();
    convex_hull();
    print();
}