Cod sursa(job #1094882)

Utilizator lilian_ciobanuLilian Ciobanu lilian_ciobanu Data 29 ianuarie 2014 22:55:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>

#define INF 4611686018427387904

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct QQ{
    long double x;
    long double y;
    long double p;
}a[120005];


bool cmp(QQ i, QQ j ){
    if(i.p == j.p){
        return i.y > j.y;
    }
    else
        return i.p < j.p;
}

int stiva[120005];

int main(){
    int n,i;
    long double x0=1000000005,y0=1000000005;

    f>>n;
    for(i=1; i<=n; ++i){
        f>>a[i].x>>a[i].y;
        if(a[i].x == x0){
        if(a[i].y < y0){
            x0=a[i].x;
            y0=a[i].y;
        }
        }
        else
        if(a[i].x < x0){
            x0=a[i].x;
            y0=a[i].y;
        }
    }

    for(i=1; i<=n; ++i){
        if(a[i].x - x0 == 0){
            a[i].p=INF;
        }
        else{
            a[i].p=(a[i].y - y0)/(a[i].x - x0);
        }

    }

    sort(a+1, a+n+1, cmp);

    a[0].x=x0;
    a[0].y=y0;
    stiva[0]=0;
    stiva[1]=1;
    stiva[2]=2;
    int st1 = 2;
    long double m;

    for(i=3; i<n; ++i){
        do{
            m=(a[stiva[st1]].y - a[stiva[st1-1]].y )*(a[i].x -a[stiva[st1]].x) - (a[i].y - a[stiva[st1]].y)*(a[stiva[st1]].x - a[stiva[st1-1]].x);
            if(m>0)
                st1--;

        }while(m>0);
        stiva[++st1]=i;
    }

    g<<fixed;
    g<<st1+1<<'\n';
    for(i=0; i<=st1; ++i){
        g.precision(6);
        g<<a[stiva[i]].x<<' '<<a[stiva[i]].y<<'\n';

    }


return 0;
}