Cod sursa(job #393642)

Utilizator hasegandaniHasegan Daniel hasegandani Data 9 februarie 2010 19:19:06
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>

using namespace std;

#define Nmax 120010

struct pct
{
    double x,y;
} v[Nmax];

int n,m;
int st[Nmax],vf;
double xi,yi;

void swap(int,int);
bool cmp(pct i,pct j)
{
    return ( atan2(i.y - yi,i.x - xi) < atan2(j.y - yi,j.x - xi) );
}

double det(int i,int j,int k)
{
    return ( v[i].x*v[j].y + v[j].x*v[k].y + v[k].x*v[i].y - v[k].x*v[j].y - v[j].x*v[i].y - v[i].x*v[k].y);
}

void solve()
{
    st[++vf]=1;
    v[++n]=v[1];
    
    for(int i=2;i<=n;++i)
        {
        st[++vf]=i;
        while (vf>2 && det(st[vf-2],st[vf-1],st[vf]) < 0 )
            st[--vf]=i;
        }
        
    printf("%d\n",--vf);
    for(int i=1;i<=vf;++i)
        printf("%lf %lf\n",v[ st[i] ].x,v[ st[i] ].y);
}

int main()
{
    m=1;
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        {
        scanf("%lf%lf",&v[i].x,&v[i].y);
        if (v[m].x > v[i].x)
            m=i;
        else
        if (v[m].x == v[i].x && v[m].y > v[i].y)
            m=i;
        }
    xi=v[m].x;
    yi=v[m].y;
        
    swap(m,1);
        
    sort(v+2,v+n+1,cmp);
    
    solve();
    return 0;
}

void swap(int i,int j)
{
    pct aux=v[i];
    v[i]=v[j];
    v[j]=aux;
}