Cod sursa(job #393668)

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

using namespace std;

#define nmax 120050
#define inf 1<<30

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

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

bool cmp(cetate i,cetate j)
{
    return ( (i.y - v[1].y)*(j.x - v[1].x) < (j.y - v[1].y)*(i.x - v[1].x) );
 ///   return ( atan2(i.y - v[1].y,i.x - v[1].x) < atan2(j.y - v[1].y,j.x - v[1].x) );
}


double dist(cetate,cetate);
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()
{
    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].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;
}

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