【POJ】2236 Wireless Network
2024-10-07 20:43:40
题目链接: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 ;
}
最新文章
- rsync同步
- python面向对象
- shell切割日志脚本
- hiho_1086_browser_caching
- Linux-守护进程的实现
- SQL数据库设计三范式
- Ajax编程相对路径与绝对路径
- WindowsForm 记事本 对话框
- myeclipse6.0安装svn插件
- C#数码管控件(转)
- IDA分析脱壳后丢失导入表的PE
- iOS 8 UIAlertController 和 UIAlertAction
- 线性回归和Logistic回归
- python 列表 元组 字典 集合
- Mysql学习之基础
- Devexpress GridControl 多选
- MySQL添加新用户、为用户创建数据库、为新用户分配权限
- list补充,append()、extend()、insert()、remove()、del()、pop()、分片
- (转)JavaWeb学习之Servlet(二)----Servlet的生命周期、继承结构、修改Servlet模板
- shiro实战系列(十五)之Spring集成Shiro
热门文章
- error LNK2001: 无法解析的外部符号 __imp__MessageBoxA@16
- *&;m与m的区别
- 【小知识】神经网络中的SGD优化器和MSE损失函数
- Avito Cool Challenge 2018 C - Colorful Bricks
- React 生命周期 16.0以下
- sql ibatis
- 框架_mybatis2使用注解
- Intellij IDEA gradle项目目录介绍
- Java—Map浅入
- Vue报错type check failed for prop