[hihoCoder] #1307 : 穿越禁区 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET
本题是一道考察搜索算法的题目。首先需要了解的是，多个雷达的监控区域将会有重叠的现象，多个具有重叠监控区域的雷达可以构成一片连续的监控区域，如下图所示：
图中红色虚框即为多个雷达构成的连续区域，寻找连续区域的过程可以通过搜索来实现，深度和广度优先搜索均可。
得到连续区域后，通过画图可以看出：显然，存在可以躲过所有监控区域穿过禁区的路线的充要条件是所有的连续区域在y轴方向没有完全覆盖区间[0,H]。例如，上面示意图中第二个连续区域在y轴方向上完全覆盖了区间[0,H]，因此，上图的情况是无解的，即不存在可以躲过所有雷达监控穿越进去的路线。
在搜索过程中记录连续区域y坐标的最大值和最小值来得到每个连续区域的区域上界和区域下界，如果所有的连续区域满足：区域上界不小于H，或区域下界大于0，则存在有效的路线；如果存在一个连续区域满足：区域上界不小于H，并且区域下界不大于0，则不存在有效的路线。
以上为本题解法，解答时需要注意数据溢出。
http://www.cnblogs.com/ilovezyg/p/6991716.html
作为H国的精英特工，你接到了一项任务，驾驶一辆吉普穿越布满监测雷达的禁区。为了简化题目，我们可以把禁区想象为一个左下角是(0, 0)右上角是( W, H )的长方形区域。区域中一共有 N 座雷达，其中第 i 座的坐标是(Xi,Yi )，监测范围是半径为 Ri 的圆形区域。所有在圆内和圆上的运载工具都会被监测到。
你的目标是从左到右穿越禁区。你可以选择线段(0, 0)-(0, H)上任意一点作为起点，线段(W, 0)-(W, H)上任意一点作为终点。在禁区内你可以沿任意路线行驶，只要保持始终在禁区内并且没有被雷达监测到。
给出禁区内的雷达部署方案，你需要判断是否存在满足条件的行驶路线。
输入
输入包含多组数据。
第1行是一个整数 T，表示以下有 T 组数据 (1 ≤ T ≤ 10)。
每组数据的第1行：三个整数 W, H, N (0 ≤ W, H ≤ 1000000, 1 ≤ N ≤ 1000)。
每组数据的第2-N+1行：每行三个整数Xi, Yi, Ri (0 ≤ Xi ≤ W, 0 ≤ Yi ≤ H, 1 ≤ Ri ≤ 1000000)。
输出
对于每组数据输出"YES"或者"NO"表示是否有满足条件的行驶路线。
- 样例输入
2 10 4 2 5 1 1 5 3 1 10 4 2 5 1 1 6 3 1
- 样例输出
NO YES
思路: 这道是并查集的题目, 有好多个雷达, 我们要把能够连在一起的雷达合并起来, 看其总共是否能够覆盖从上到下. 先给每个雷达默认父结点是本身, 然后依次遍历每个雷达, 如果A雷达和B雷达能够接触到, 即他们圆心距离小于两个半径之和, 说明他们在一个集合里面, 就把B的最深父结点设置为A的最深父结点. 这样做完之后, 再依次将每个雷达的父结点设为本身的最深父结点, 就可以知道总共有几个集合, 然后计算每个集合所覆盖的范围是多少即可.
int main()
{
vector<pair<int ,int> > vec;
int T, W, H, N, xi, yi, ri;
cin >> T;
while(T--)
{
cin >> W >> H >> N;
vector<vector<int> > radars;
for(int i = 0; i < N; i++)
{
cin >> xi >> yi >> ri;
radars.push_back(vector<int>{xi, yi, ri});
}
int ans = 1;
vector<int> hash(N);
for(int i = 0; i < N ;i++) hash[i] = i;
for(int i =0; i< N; i++)
{
int x1 = radars[i][0], y1 = radars[i][1], r1 = radars[i][2];
for(int j = i+1; j < N; j++)
{
int x2 = radars[j][0], y2 = radars[j][1], r2 = radars[j][2];
float dis = sqrt(pow(x1-x2, 2)+ pow(y1-y2, 2));
if(dis <= r1+r2)
{
int par1 = hash[j], par2 = hash[i];
while(hash[par1] != par1) par1 = hash[par1];
while(hash[par2] != par2) par2 = hash[par2];
hash[par1] = par2;
}
}
}
set<int> parent;
for(int i =0; i< N; i++)
{
int par = hash[i];
while(par != hash[par]) par = hash[par];
hash[i] = par;
parent.insert(par);
}
for(int val: parent)
{
int top = INT_MIN, bot = INT_MAX;
for(int i = 0; i < N; i++)
{
if(hash[i] == val)
{
top = max(top, radars[i][1] + radars[i][2]);
bot = min(bot, radars[i][1] - radars[i][2]);
if(top >= H && bot <=0)
{
ans = 0;
i = N;
break;
}
}
}
if(ans == 0) break;
}
if(ans) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
http://www.voidcn.com/blog/octopusflying/article/p-6644282.html本题是一道考察搜索算法的题目。首先需要了解的是，多个雷达的监控区域将会有重叠的现象，多个具有重叠监控区域的雷达可以构成一片连续的监控区域，如下图所示：
得到连续区域后，通过画图可以看出：显然，存在可以躲过所有监控区域穿过禁区的路线的充要条件是所有的连续区域在y轴方向没有完全覆盖区间[0,H]。例如，上面示意图中第二个连续区域在y轴方向上完全覆盖了区间[0,H]，因此，上图的情况是无解的，即不存在可以躲过所有雷达监控穿越进去的路线。
在搜索过程中记录连续区域y坐标的最大值和最小值来得到每个连续区域的区域上界和区域下界，如果所有的连续区域满足：区域上界不小于H，或区域下界大于0，则存在有效的路线；如果存在一个连续区域满足：区域上界不小于H，并且区域下界不大于0，则不存在有效的路线。
以上为本题解法，解答时需要注意数据溢出。
private static class Radar {
int x;
int y;
int r;
boolean visited;
}
/**
* Input data.
*/
@SuppressWarnings("unused")
private static int T, W, H, N;
/**
* Radar list.
*/
private static Radar[] radars;
/**
* For input.
*/
private static Scanner scan;
/**
* Record the range.
*/
private static int min, max;
/**
* The main program.
*
* @param args
* The command-line parameters list.
*/
public static void main(String[] args) {
scan = new Scanner(System.in);
T = scan.nextInt();
for (int i = 0; i < T; i++) {
function();
}
scan.close();
}
/**
* Deals with one test case.
*/
private static void function() {
W = scan.nextInt();
H = scan.nextInt();
N = scan.nextInt();
radars = new Radar[N];
for (int i = 0; i < N; i++) {
radars[i] = new Radar();
radars[i].x = scan.nextInt();
radars[i].y = scan.nextInt();
radars[i].r = scan.nextInt();
radars[i].visited = false;
}
for (int i = 0; i < N; i++) {
if (!radars[i].visited) {
max = Integer.MIN_VALUE;
min = Integer.MAX_VALUE;
dfs(i);
if(min <= 0 && max >= H) {
System.out.println("NO");
return;
}
}
}
System.out.println("YES");
}
/**
* Use DFS to find the answer of this problem.
*
* @param radar
* The current radar to search;
*/
private static void dfs(int index) {
Radar radar = radars[index];
radar.visited = true;
if (max < radar.y + radar.r) {
max = radar.y + radar.r;
}
if (min > radar.y - radar.r) {
min = radar.y - radar.r;
}
for (int j = 0; j < N; j++) {
if (!radars[j].visited) {
Radar rj = radars[j];
long x1 = (long) radar.x;
long x2 = (long) rj.x;
long y1 = (long) radar.y;
long y2 = (long) rj.y;
long r1 = (long) radar.r;
long r2 = (long) rj.r;
if (Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2) <=
Math.pow(r1 + r2, 2)) {
dfs(j);
}
}
}
}
http://www.cnblogs.com/ilovezyg/p/6991716.html
把上、下边界以及N个圆抽象成N+2个图节点，当边界与圆或圆与圆之间相交时表示它们连通，问题就转变为判断从上边界到下边界是否存在路径。建图后从上边界跑一遍DFS即可。
Read full article from [hihoCoder] #1307 : 穿越禁区 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET