Cod sursa(job #371738)

Utilizator hasegandaniHasegan Daniel hasegandani Data 6 decembrie 2009 17:57:02
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>

using namespace std;

#define nmax 120050
#define inf 0x3f3f3f3f

struct cetate
{
    double x,y,p;
} v[nmax];

int n,m=0,st[nmax],vf;
double dx,dy;

int cmp(cetate i,cetate j)
{
    return (i.p < j.p);
}

void init();
void cit();
void solve();
void swap(int,int);

double det(cetate i,cetate j,cetate k)
{
    return (i.x*j.y + j.x*k.y + k.x*i.y - j.y*k.x - k.y*i.x - i.y*j.x);
}

int main()
{
    cit();
    
    init();
        
    solve();
    
    return 0;
}

void init()
{
    swap(1,m);
    
    for(int i=2;i<=n;++i)
        {
        dx=v[i].x-v[1].x;
        dy=v[i].y-v[1].y;
        if (dx>0)
            v[i].p=atan((double)dy/dx);
        if (dx==0)
            v[i].p=M_PI_2;
        if (dx<0)
            v[i].p=atan((double)dy/dx) + M_PI;
  //      printf("(%d,%d) : %.5lf\n",v[i].x,v[i].y,v[i].p);
        }
        
    sort(v+2,v+n+1,cmp);
}

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

void cit()
{
    v[0].x=inf; v[0].y=inf;
    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].y > v[i].y)
            m=i;
        else
        if (v[m].y == v[i].y && v[m].x > v[i].x)
            m=i;
               
        }
}

void swap(int i,int j)
{
    double aux=v[i].x;
    v[i].x=v[j].x;
    v[j].x=aux;
    
    aux=v[i].y;
    v[i].y=v[j].y;
    v[j].y=aux;
}