Cod sursa(job #1589904)

Utilizator gapdanPopescu George gapdan Data 4 februarie 2016 15:54:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<cstdio>
#include <algorithm>
#define NMAX 130005

using namespace std;

struct punct
{
    double x,y;
}v[NMAX],st[NMAX],X;
int n,i,k,poz;
double panta(punct a, punct b, punct c)
{
    return(b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
bool cmp(punct a,punct b)
{
    return panta(v[1],a,b)<0;
}

int main()
{
    ifstream f("infasuratoare.in");
    freopen("infasuratoare.out","w",stdout);
    f>>n;
    f>>v[1].x>>v[1].y;
    X.x=v[1].x;X.y=v[1].y;
    poz=1;
    for(i=2;i<=n;++i)
    {
        f>>v[i].x>>v[i].y;
        if(v[i].y<X.y) {X=v[i];poz=i;}
            else if (v[i].y == X.y && v[i].x<X.x) {X=v[i];poz=i;}
    }
    swap(v[poz],v[1]);
    sort(v+2,v+n+1,cmp);
    st[1]=v[1];st[2]=v[2];k=2;
    for(i=3;i<=n;++i)
    {
        while(k >=2 && panta(st[k-1],st[k],v[i])>0) --k;
        ++k;
        st[k]=v[i];
    }
    printf("%d\n",k);
    for(i=k;i>=1;--i)
    {
        printf("%.9lf %.9lf\n",st[i].x,st[i].y);
    }
    return 0;


}