cpp1.cpp

黑白点的匹配贪心算法 设平面上分布着n个白点和n个黑点

#include "iostream.h"
#include "math.h"
struct point
{
	double x,y;
};
void sort(point *a,int n)
{
	int i,j;point p;
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(a[i].x>a[j].x||(a[i].x==a[j].x&&(a[i].y>a[j].y)))
			{
				p=a[i];
				a[i]=a[j];
				a[j]=p;
			}
		}
	}
}
double dis(point pointw,point pointb)
{
	double dist;
	dist=sqrt(pow((pointb.x-pointw.x),2)+pow((pointb.y-pointw.y),2));
	return dist;
}
int main()
{
	int i,j,n,k;
	cin>>n;
	point *pointw=new point[n];
	point *pointb=new point[n];
	int *b=new int[n];
	for(i=1;i<=n;i++)
		cin>>pointb[i].x;
	for(i=1;i<=n;i++)
		cin>>pointb[i].y;
	for(i=1;i<=n;i++)
		cin>>pointw[i].x;
	for(i=1;i<=n;i++)
		cin>>pointw[i].y;
	sort(pointw,n);
	for(i=1;i<=n;i++)
		b[i]=1;
	int count=0;
	for(i=1;i<=n;i++)
	{
		double mindis=32767;
		double Min=mindis;
		for(j=1;j<=n;j++)
		{
			if(b[j]!=0&&pointb[j].x>=pointw[i].x&&pointb[j].y>=pointw[i].y)
			{
				if(mindis>dis(pointw[i],pointb[j]))
				{
					mindis=dis(pointw[i],pointb[j]);
					k=j;
				}
			}
		}
		if(mindis<Min)
		{
			b[k]=0;
			count++;
			cout<<pointw[i].x<<","<<pointw[i].y<<" & "<<pointb[k].x<<","<<pointb[k].y<<endl;
		}
	}
	cout<<"最大匹配数："<<count<<endl;
	return 0;
}