# 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.