2318.txt

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

#define debug 0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000
#define NMAX 5000
int sum[NMAX]={0};
int n,m;
int U[NMAX],L[NMAX];
int cross(int x1,int y1,int x2,int y2)
{
	return x1*y2 - x2*y1;
}
int main()
{

#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i,j;	
	int x1,y1,x2,y2,x,y;
	scanf("%d",&n);
	while(n)
	{
		scanf("%d",&m);
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		memset(sum,0,sizeof(sum));
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&U[i],&L[i]);
		}
		U[i]=x2;
		L[i]=x2;
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&x,&y);
			for(j=0;j<=n;j++)
			{
				if(cross(x-L[j],y-y2,U[j]-L[j],y1-y2)<0)
				{
					sum[j]++;
					break;
				}
			}
		}
		for(i=0;i<=n;i++)
		{
			printf("%d: %d\n",i,sum[i]);
		}
		printf("\n");
		scanf("%d",&n);
	}

#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}