main.cpp

黑白点匹配问题

#include "stdio.h"
#define MAXSIZE 100
#define MIN -5000

typedef struct point{
	float elemX;
	float elemY;
	int visit;
}point;

int main()
{
	int index(point black[],point white[],int n);
	int k=1,l;//测试数据个数
	int n;//点的个数
	int i;//用于循环
	point black[MAXSIZE],white[MAXSIZE];
	scanf("%d",&l);
	while(k<=l)
	{
		scanf("%d",&n);
		black[0].elemX=MIN;
		black[0].elemY=MIN;
		black[n+1].elemX=MIN;
		black[n+1].elemY=MIN;
		white[0].elemX=MIN;
		white[0].elemY=MIN;
		for(i=1;i<=n;i++)
		{
			black[i].visit=0;
			scanf("%f%f",&black[i].elemX,&black[i].elemY);
		}
		for(i=1;i<=n;i++)
		{
			white[i].visit=0;
			scanf("%f%f",&white[i].elemX,&white[i].elemY);
		}
		index(black,white,n);
		k++;
	}
	return 1;
}


/*******************************
*   归并排序
*   来源：严蔚敏编写的数据结构 *
*******************************/
 void Merge(point SR[],point TR[],int i,int m,int n)
 { /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12 */
	 //TR[]为辅助数组
   int j,k,l;
   for(j=m+1,k=i;i<=m&&j<=n;++k) /* 将SR中记录由小到大地并入TR */
     if (SR[i].elemX>=SR[j].elemX)
	 {
       TR[k].elemX=SR[i].elemX;
	   TR[k].elemY=SR[i].elemY;
	   TR[k].visit=SR[i].visit;
	   i++;
	 }
     else
	 {
       TR[k].elemX=SR[j].elemX;
	   TR[k].elemY=SR[j].elemY;
	   TR[k].visit=SR[j].visit;
	   j++;
	 }
   if(i<=m)
     for(l=0;l<=m-i;l++)
	 {
       TR[k+l].elemX=SR[i+l].elemX; 
	   TR[k+l].elemY=SR[i+l].elemY; 
	   TR[k+l].visit=SR[i+l].visit; 
	 }/* 将剩余的SR[i..m]复制到TR */
   if(j<=n)
     for(l=0;l<=n-j;l++)
	 {
       TR[k+l].elemX=SR[j+l].elemX; 
	   TR[k+l].elemY=SR[j+l].elemY;
	   TR[k+l].visit=SR[j+l].visit;
	 }/* 将剩余的SR[j..n]复制到TR */
//   for(i=1;i<=n;i++)
//	   SR[i]=TR[i];
 }

 void MSort(point SR[],point TR1[],int s, int t)
 { /* 将SR[s..t]归并排序为TR1[s..t]。算法10.13 */
   int m;
   point TR2[MAXSIZE+1];
   if(s==t)
   {
     TR1[s].elemX=SR[s].elemX;
	 TR1[s].elemY=SR[s].elemY;
	 TR1[s].visit=SR[s].visit;
   }
   else
   {
     m=(s+t)/2; /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
     MSort(SR,TR2,s,m); /* 递归地将SR[s..m]归并为有序的TR2[s..m] */
     MSort(SR,TR2,m+1,t); /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
     Merge(TR2,TR1,s,m,t); /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
   }
 }

/*****************************
*   具体匹配算法             *
*****************************/


int index(point black[],point white[],int n)
{
	int i=1,j=1;//用与循环
	int k=0;//用于记数
	int flag=0;
//	float BtempX,BtempY;//临时存放黑子的横坐标和纵坐标
//	float WtempX,WtempY;//临时存放白子的横纵坐标
	int MAX=0;//用于存放当X坐标相同时的最大纵坐标的下标位置
	MSort(black,black,1,n);
	MSort(white,white,1,n);//对黑子和白子按横坐标从大到小排序
	for(i=n;i>0;i--)
	{
//		flag=0;
//		BtempX=black[i].elemX;
//		BtempY=black[i].elemY;
		black[i].visit=1;
		MAX=0;
		j=n;
		while(j>0)
		{	
			if(!white[j].visit)
			{
/*				if(white[j].elemX>=black[i+1].elemX)
				{
					if(white[j].elemX<=black[i].elemX
						&&white[j].elemY>=white[MAX].elemY
						&&white[j].elemY<=black[i].elemY)
					{
						flag=1;
						MAX=j;
					}
				}
				else 
				{
					if(flag) break;
					if(white[j].elemY<=black[i].elemY
						&&white[j].elemY>=white[MAX].elemY)
						MAX=j;
				}*/
				if(white[j].elemX<=black[i].elemX
					&&white[j].elemY>=white[MAX].elemY
					&&white[j].elemY<=black[i].elemY)
					MAX=j;
			}
			j--;
		}
		if(!white[MAX].visit&&MAX)
		{
			white[MAX].visit=1;
			k++;
		}
	}
	printf("%d\n",k);
	return 1;
}