题目链接http://poj.org/problem?id=2236

题意:给你n台计算机的坐标。d是可通信的最大距离。有两个操作。

1、O p 表示修复计算机p.

2、S p q表示询问pq是否能够通信。

题解:并查集的提升。把距离考虑在判断内。如果修复了p就对当前集合做一个并操作。查找的时候直接判断父亲是不是共同的即可。

代码:

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define ll long long
using namespace std;
const int maxn = ; int dx[maxn],dy[maxn];
int f[maxn],vis[maxn];
int n,d; int dis(int a,int b){
int distance = (dx[a]-dx[b]) * (dx[a] - dx[b]) + (dy[a]-dy[b]) * (dy[a] - dy[b]);
if(distance <= d*d) return true;
else return false;
} void init(int n){
for(int i = ; i <= n; i++)
f[i] = i,vis[i] = ;
} int find(int x){
if(x == f[x])
return x;
return f[x] = find(f[x]);
} void join(int a, int b){
a = find(a);
b = find(b);
if(a != b){
f[a] = b;
}
} int main(){ cin>>n>>d;
for(int i = ; i < n ;i++){
cin>>dx[i]>>dy[i];
} init(n);
char ch;
int num;
int cnt = ;
while(cin>>ch){
if(ch == 'O'){
cin>>num;
num--;
vis[cnt++] = num;
for(int i = ; i < cnt-; i++){
if(vis[i] != num && dis(vis[i],num)){
join(vis[i],num);
}
}
}
else{
int p,q;
cin>>p>>q;
if(find(p-) == find(q-)){
cout<<"SUCCESS"<<endl;
}
else{
cout<<"FAIL"<<endl;
}
}
}
return ;
}

最新文章

  1. rsync同步
  2. python面向对象
  3. shell切割日志脚本
  4. hiho_1086_browser_caching
  5. Linux-守护进程的实现
  6. SQL数据库设计三范式
  7. Ajax编程相对路径与绝对路径
  8. WindowsForm 记事本 对话框
  9. myeclipse6.0安装svn插件
  10. C#数码管控件(转)
  11. IDA分析脱壳后丢失导入表的PE
  12. iOS 8 UIAlertController 和 UIAlertAction
  13. 线性回归和Logistic回归
  14. python 列表 元组 字典 集合
  15. Mysql学习之基础
  16. Devexpress GridControl 多选
  17. MySQL添加新用户、为用户创建数据库、为新用户分配权限
  18. list补充,append()、extend()、insert()、remove()、del()、pop()、分片
  19. (转)JavaWeb学习之Servlet(二)----Servlet的生命周期、继承结构、修改Servlet模板
  20. shiro实战系列(十五)之Spring集成Shiro

热门文章

  1. error LNK2001: 无法解析的外部符号 __imp__MessageBoxA@16
  2. *&amp;m与m的区别
  3. 【小知识】神经网络中的SGD优化器和MSE损失函数
  4. Avito Cool Challenge 2018 C - Colorful Bricks
  5. React 生命周期 16.0以下
  6. sql ibatis
  7. 框架_mybatis2使用注解
  8. Intellij IDEA gradle项目目录介绍
  9. Java—Map浅入
  10. Vue报错type check failed for prop