学步园

  很典型的一道并查集，动态的判断距离足够近的点就归为一类。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Node
{
public:
	Node()
	{
		x=y=0.0f;
		nodeID=-1;
		parent=NULL;
		rank=0;
	}
	Node(double xi,double yi,int id)
	{
		x=xi;
		y=yi;
		nodeID=id;
		parent=NULL;
	}
	Node(double xi,double yi)
	{
		x=xi;
		y=yi;
		parent=NULL;
	}
	double x,y;
	int nodeID;
	Node* parent;
	int rank;
};
//并查集几个基本函数
void MakeSet(Node* node)
{
	node->parent=node;
	node->rank=0;
	return;
}

Node* FindSet(Node* pNode)
{
	if(pNode->parent!=pNode)
	{
		pNode->parent=FindSet(pNode->parent);
	}
	return pNode->parent;
}

void LinkSets(Node* pNode1,Node* pNode2)
{
	if(pNode1->rank>pNode2->rank)
	{
		pNode2->parent=pNode1;
	}
	else if(pNode1->rank<pNode2->rank)
	{
		pNode1->parent=pNode2;
	}
	else
	{
		pNode1->parent=pNode2;
		pNode2->rank++;
	}
	return;
}


void UnionSets(Node *pNode1,Node *pNode2)
{
	LinkSets(FindSet(pNode1),FindSet(pNode2));
	return;
}


double Distance(Node node1,Node node2)
{
	return sqrt( pow(node1.x-node2.x,2) + pow(node1.y-node2.y,2) );
}

int main()
{
	Node* allNodeVec[1002];
	Node* repairedNodeVec[1002];
	int n,d;
	
	scanf("%d%d",&n,&d);
	double xi,yi;
	for(int i=0;i<n;i++)
	{
		scanf("%lf%lf",&xi,&yi);
		allNodeVec[i]=new Node(xi,yi,i+1);
		MakeSet(allNodeVec[i]);
	}
	int iRepNum=0;//See how many computers have been repaired.
	char opera;
	while(scanf("%c",&opera)!=EOF)
	{
		if(opera=='O')
		{
			int newNodeId=-1;
			scanf("%d",&newNodeId);
			for(int i=0;i!=iRepNum;i++)
			{
				if(Distance(*allNodeVec[newNodeId-1],*repairedNodeVec[i])<= d)
				{
					if(FindSet(allNodeVec[newNodeId-1])!= FindSet(repairedNodeVec[i]) )
					{
						UnionSets(allNodeVec[newNodeId-1],repairedNodeVec[i]);
					}
				}
			}
			repairedNodeVec[iRepNum]=allNodeVec[newNodeId-1];
			iRepNum++;
		}

		else if(opera=='S')
		{
			int ai,bi;
			scanf("%d%d",&ai,&bi);
			if(FindSet(allNodeVec[ai-1]) == FindSet(allNodeVec[bi-1]))
			{
				printf("SUCCESS\n");
			}
			else
			{
				printf("FAIL\n");
			}

		}
	}

}