Poj Solution 2007

http://poj.org/problem?id=2007

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define debug 0
#define INF 1000
#if debug
    #define NMAX 10
#else
    #define NMAX 52
#endif
int point[NMAX][2];
int base[2];
int m[5];
int qu(int p[])
{
    if(p[0]>0&&p[1]>0)
        return 1;
    if(p[0]<0&&p[1]>0)
        return 2;
    if(p[0]<0&&p[1]<0)
        return 3;
    if(p[0]>0&&p[1]<0)
        return 4;
    return 0;
}
int product(int a[],int b[])
{
    return a[0]*b[1]-a[1]*b[0];
}

int cmp(const void *a,const void *b)
{

    
    int p1[2],p2[2];
    if(m[qu((int*)a)]==m[qu((int*)b)])
    {
        p1[0]=((int*)a)[0];
        p2[0]=((int*)b)[0];
        p1[1]=((int*)a)[1];
        p2[1]=((int*)b)[1];
        return -product(p1,p2);
    }
    else
    return m[qu((int*)a)]-m[qu((int*)b)];
            
    
}
int findbase(int flag[])
{
    int i,j;
    for(i=1;i<=4;i++)
    {
        if(!flag[i])
        {
            i++;
            while(!flag[i])
                i++;
            break;
        }
    }
    int k=1;
    for(j=i;j<=i+3;j++)
    {
        m[(j-1)%4+1]=k++;
    }
    return 0;
}


int main()
{
#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
       int i;
    int flag[5]={0};
    
       int n;
       i=0;
       n=0;
       while(scanf("%d%d",&point[i][0],&point[i][1])!=EOF)
       {
           flag[qu(point[i])]=1;
           i++;
       }
       findbase(flag);
       n=i;
       qsort((void*)(point+1),n-1,2*sizeof(int),cmp);
       for(i=0;i<n;i++)
       {
           printf("(%d,%d)n",point[i][0],point[i][1]);
       }
       

#if debug
    fclose(stdin);
    fclose(stdout);
#endif
    return 1;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *