Cod sursa(job #1110358)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 17 februarie 2014 23:44:30
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct punct {
    double x;
    double y;
}v[120010];

int i, p,s[120010],n,imin;

double minim,aux1,aux2;

int arie (punct i, punct j, punct k) {

    double ariec = (j.x-i.x)*(k.y-i.y)-(k.x-i.x)*(j.y-i.y);
    if (ariec<0.000000000001)
        return 1;
    else
        return 0;

}

int cmp (punct a, punct b) {

    return arie(v[1],a,b);

}

int main () {

    fin>>n;
    minim=1000000000;
    for (i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        if (v[i].x<minim) {
            minim=v[i].x;
            imin=i;
        }else
            if (v[i].y<v[imin].y)
                imin=i;
    }

    aux1=v[1].x;aux2=v[1].y;
    v[1].x=v[imin].x;v[1].y=v[imin].y;
    v[imin].x=aux1;v[imin].y=aux2;

    sort (v+2,v+n+1,cmp);



    s[1]=n;
    s[2]=n-1;

    p=2;
    for (i=n-2;i>=1;i--) {
        while( arie (v[s[p-1]],v[s[p]],v[i]) && p>=1  )
            p--;
        s[++p]=i;
    }
    fout<<p<<"\n";
    fout << setprecision(6) << fixed;
    for (i=1;i<=p;i++)
        fout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";

    return 0;
}