Cod sursa(job #904915)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 4 martie 2013 23:38:10
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <algorithm>
#include <fstream>
#include <iomanip>

using namespace std;

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

const double eps= 1e-12;
const int nmax= 120000;

inline double abs(double x){
    if (x>=0){
        return x;
    }else{
        return -x;
    }
}

struct pt{
    double x, y;
};
struct pt_cmp{
    bool operator()(pt x, pt y){
        if (abs(x.x-y.x)<=eps){
            return x.y<y.y;
        }else{
            return x.x<y.x;
        }
    }
};
pt v[nmax+1];

double area(pt x, pt y, pt z){
    return x.x*y.y+y.x*z.y+z.x*x.y-
        x.x*z.y-y.x*x.y-z.x*y.y;
}

int u[nmax+1], l[nmax+1];
pt v_aux[nmax+1];

int main(){
    int n;
    fin>>n;
    for (int i= 1; i<=n; ++i){
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1, v+n+1, pt_cmp());
    
    u[0]= 1; u[1]= 1;
    l[0]= 1; l[1]= 1;
    for (int i= 2; i<=n; ++i){
        while (u[0]>=2&& area(v[u[u[0]-1]], v[u[u[0]]], v[i])<eps){
            --u[0];
        }
        ++u[0]; u[u[0]]= i;
        while (l[0]>=2&& area(v[l[l[0]-1]], v[l[l[0]]], v[i])>eps){
            --l[0];
        }
        ++l[0]; l[l[0]]= i;
    }
    for (int i= 1; i<=l[0]; ++i){
        v_aux[i]= v[l[i]];
    }
    for (int i= u[0]-1; i>1; --i){
        v_aux[l[0]+u[0]-i]= v[u[i]];
    }
    n= l[0]+u[0]-2;
    fout<<n<<"\n";
    fout<<setprecision(12)<<fixed;
    for (int i= n; i>0; --i){
        v[i]= v_aux[n-i+1];
        fout<<v[i].x<<" "<<v[i].y<<"\n";
    }

    return 0;
}