[hihoCoder] #1307 : 穿越禁区 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET

[hihoCoder] #1307 : 穿越禁区 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET

作为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"表示是否有满足条件的行驶路线。

Read full article from [hihoCoder] #1307 : 穿越禁区 解题报告 - Jonah的专栏 - 博客频道 - CSDN.NET