Cod sursa(job #690051)

Utilizator bogfodorBogdan Fodor bogfodor Data 25 februarie 2012 09:43:17
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <cstdio>
#include <algorithm>
#define INF 100000000
#define Lmax 120000

using namespace std;

struct punct{
    double x;
    double y;
    long double p;
}a[Lmax],st[Lmax];

int n;
int pi=0;

FILE *fin=freopen("infasuratoare.in","r",stdin);
FILE *fout=freopen("infasuratoare.out","w",stdout);

long double panta(int i)
{
    if(a[i].x == a[pi].x)
        return INF;
    return(a[i].y-a[pi].y)/(a[i].x-a[pi].x);
}

void citire()
{
    a[pi].x=INF;
    a[pi].y=INF;
    scanf("%d ",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf %lf",&a[i].x,&a[i].y);
        if(a[i].x<a[pi].x || a[i].x==a[pi].x && a[i].y<a[pi].y)
         pi=i;
    }
    a[0]=a[pi];
    a[pi]=a[n];
    n--;

}

bool cmp(punct a, punct b)
{
    if(a.p<b.p)
        return true;
    return false;
}

void fapante()
{
    pi=0;
    for(int i=1;i<=n;i++)
        a[i].p=panta(i);
    sort(a+1,a+n+1,cmp);
}

double det(punct a, punct b, punct c)
{
    double D=a.x*b.y +c.x*a.y + b.x*c.y;
    D-=(a.x*c.y+c.x*b.y + b.x*a.y);
    if(D>=0)
        return 1;
    return 0;
}
int t=0;

void solve()
{
    st[t++]=a[0];
    st[t++]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(det(st[t-2],st[t-1],a[i]))
            st[t++]=a[i];
        else{
            while(!det(st[t-2],st[t-1],a[i])){
                st[--t]=a[i];
            }
             t++;
        }
    }
}

void afisare()
{
    printf("%d\n",t);
    for(int i=1;i<t;++i)
        printf("%lf %lf\n",st[i].x,st[i].y);
    printf("%lf %lf\n",st[0].x,st[0].y);
}

int main()
{
    citire();
    fapante();
    solve();
    afisare();
    return 0;
}