POJ 2236

• 2层循环找出每个点 周围与其距离<=d的点，vector<int> p[maxn]记录,
• O的意思是修复O附近的点,但是必须是已经出现过的需要被修复的点,(从样例我们可以看出来),用vis[]标记一下需要修复的点,
• 其他的就是并查集了

  #include <iostream>
  #include <vector>
  #include <cmath>
  using namespace std;
  const int maxn = 1e3+10;
  int n,d;
  struct node {
  	int x,y;
  } e[maxn];
  vector<int> p[maxn];
  int pre[maxn];
  bool vis[maxn];
  void process() {
  	for (int i=1; i<=n; i++) {
  		for (int j=1; j<=n; j++) {
  			if (i == j) continue;
  			double dx = e[i].x - e[j].x;
  			double dy = e[i].y - e[j].y;
  			if (sqrt(dx*dx+dy*dy) <= d) {
  				p[i].push_back(j);
  			}
  		}
  	}
  }
  int find(int x) {
  	if (x == pre[x]) return x;
  	return pre[x] = find(pre[x]);
  }
  void init() {
  	for (int i=1; i<=n; i++) pre[i] = i;
  }
  void merge(int x) { //修复x周围的点
  	int rx = find(x);
  	for (int i=0; i<p[x].size(); i++) {
  		int ra = find(p[x][i]);
  		if (rx == ra) continue;
  		if(vis[p[x][i]]) pre[ra] = rx;
  	}
  }
  bool query(int a,int b) {
  	return find(a)==find(b);
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	scanf("%d%d",&n,&d);
  	for (int i=1; i<=n; i++) {
  		scanf("%d%d",&e[i].x,&e[i].y);
  	}
  	init();
  	process();
  	
  	/*for (int i=1; i<=n; i++) 
  		for (int j=0; j<p[i].size();j++) 
  			printf("cur=%d to=%d\n",i,p[i][j]);
  	*/
  	char ch;
  	while (scanf("\n%c",&ch) != EOF) {
  		if (ch == 'O') {
  			int x;
  			vis[x] = 1;
  			scanf("%d",&x);
  			merge(x);
  			/*printf("merge:%d \n",x);
  			for (int i=1; i<=n; i++)
  				printf("%d ",pre[i]);*/
  		}
  		else {
  			int a,b;
  			scanf("%d%d",&a,&b);
  			if (query(a,b)) 
  				printf("SUCCESS\n");
  			else 
  				printf("FAIL\n");
  		}
  	}
  	return 0;
  }