2007.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#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;
}