Cod sursa(job #1002684)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 28 septembrie 2013 15:40:26
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, i, ind, k;

struct puncte{
    double x, y, r;
} v[120010], p, aux, st[120010];

bool cmp(puncte a, puncte b){
    return a.r<b.r;
}

double afla(puncte a, puncte b, puncte c){
    return (a.x*b.y+b.x*c.y+c.x*a.y)-(c.x*b.y+c.y*a.x+b.x*a.y);
}

int main(){
    f>>n;
    p.y=p.x=1000000010;
    for(i=1; i<=n; i++)
    {
        f>>v[i].x>>v[i].y;
        v[i].r=v[i].y/v[i].x;
        if(v[i].x<p.x || (v[i].x==p.x && v[i].y<p.y) )
        {
            p=v[i];
            ind=i;
        }
    }
    aux=v[1];
    v[1]=v[ind];
    v[ind]=aux;
    sort(v+2, v+n+1, cmp);
    /*for(i=1; i<=n; i++)
        g<<v[i].x<<' '<<v[i].y<<"\n";*/
    st[++k]=v[1];
    st[++k]=v[2];
    for(i=3; i<=n; i++)
    {
        while(k>=2 && afla(st[k-1], st[k], v[i])<0)
            k--;
        st[++k]=v[i];
    }
    g<<k<<"\n"<<fixed;
    for(i=1; i<=k; i++)
        g<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
    return 0;
}