[UVA][二分&BFS] 10876 - Factory Robot
Problem G
Factory Robot
Input File: Standard Input
Output: Standard Output
In a factory hall (size 1000 x 1000 meters) there are a number of circular pillars having various radii. The pillars don't touch each other or the walls. The company owning the factory is planning to buy a guard robot, which is to move around in the hall. In the four corners of the hall there are machines which the guard robot must be able to reach by zigzagging between the pillars and the walls (the machines themselves are no obstacles).
All guard robots available for sale are also circular. Before the company decides which robot to buy, they want to find out the maximum radius size it can have, so that it is still able to reach all four machines.
No part of the robot may extend outside the hall. If the robot has radius r, then it must be able to reach the coordinates (r,r), (1000-r,r), (r,1000-r) and (1000-r,1000-r), from where it can reach the four machines. The diameter of the robot must be less than the shortest distance between a pillar and a corner.
Input
The first line in the input contains the number of test cases (at most 20). Each case starts with a line containing a single integer N, the number of pillars (1 <= N <= 200). Then follows N lines. Each such line contains three integers x, y and r: the coordinates (x,y) and radius (r) of a pillar (1 < x, y < 999, 1 <= r <= 499).
Output
For each test case, output a line containing a single floating point value: the maximum radius of the guard robot. The number should be printed with exactly three decimal digits (rounded correctly).
Sample Input Output for Sample Input
13 165 520 110560 430 30
590 115 75 |
132.562
|
Problem setter: Jimmy Mårdell
Special Thanks: Derek Kisman
題目描述：
在一個 1000 x 1000 的座標中，圓柱當作障礙物，圓柱不會超過邊界。
而現在有警衛機器人要巡邏這矩形四個角，機器人可當作一個圓進行移動。
移動時不可碰撞到其他柱子，同時必須符合可以探測到四個角的條件。
條件：機器人切於角落的兩邊，也就是題目描述的 (r,r),(1000-r, 1000-r) ...
//這是機器人圓心必須經過的點。
問機器人的半徑 r，最大為何？
題目解法：
考慮二分答案，對半徑 r 採用 BFS 檢查。
BFS 檢查為：(先考慮必須機器人能塞到四個角！)
再者是必須建圖，這個圖定義為阻礙的路線。
四條邊也算四個點，查看是否有任兩點(四條邊的點)連線了！
也就是說其中兩點連線時，至少會有一個角落無法移動到。
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
int x[205], y[205], r[205];
double dist[205][205];
int visited[205];
vector<int> g[205];
void dfs(int nd) {
if(visited[nd]) return;
visited[nd] = 1;
int i;
for(i = 0; i < g[nd].size(); i++)
dfs(g[nd][i]);
}
int check(double R, int n) {
int i, j, k;
for(i = 0; i < n+4; i++)
g[i].clear();
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
if(i == j) continue;
if(dist[i][j]-r[i]-r[j] <= 2*R) {
g[i].push_back(j);
}
}
if(hypot(x[i]-R, y[i]-R) <= R+r[i])
return 1;
if(hypot(x[i]-(1000-R), y[i]-R) <= R+r[i])
return 1;
if(hypot(x[i]-R, y[i]-(1000-R)) <= R+r[i])
return 1;
if(hypot(x[i]-(1000-R), y[i]-(1000-R)) <= R+r[i])
return 1;
if(x[i]-r[i]-2*R <= 0) {
g[i].push_back(n);
g[n].push_back(i);
}
if(x[i]+r[i]+2*R >= 1000) {
g[i].push_back(n+1);
g[n+1].push_back(i);
}
if(y[i]-r[i]-2*R <= 0) {
g[i].push_back(n+2);
g[n+2].push_back(i);
}
if(y[i]+r[i]+2*R >= 1000) {
g[i].push_back(n+3);
g[n+3].push_back(i);
}
}
memset(visited, 0, sizeof(visited));
dfs(n);
if(visited[n+1] || visited[n+2] || visited[n+3])
return 1;
memset(visited, 0, sizeof(visited));
dfs(n+1);
if(visited[n] || visited[n+2] || visited[n+3])
return 1;
memset(visited, 0, sizeof(visited));
dfs(n+2);
if(visited[n+1] || visited[n] || visited[n+3])
return 1;
memset(visited, 0, sizeof(visited));
dfs(n+3);
if(visited[n+1] || visited[n+2] || visited[n])
return 1;
return 0;
}
int main() {
int testcase, n;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
double ll, rr, mid;
scanf("%d", &n);
ll = 0, rr = 500;
for(i = 0; i < n; i++) {
scanf("%d %d %d", &x[i], &y[i], &r[i]);
/*rr = min(rr, hypot(x[i], y[i]));
rr = min(rr, hypot(x[i], y[i]-1000));
rr = min(rr, hypot(x[i]-1000, y[i]));
rr = min(rr, hypot(x[i]-1000, y[i]-1000));*/
}
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
dist[i][j] = hypot(x[i]-x[j], y[i]-y[j]);
//rr /= 2;
int cnt = 0;
while(++cnt < 30) {
mid = (ll+rr)/2;
int f = check(mid, n);
if(f == 0)
ll = mid;
else
rr = mid;
}
printf("%.3lf\n", mid);
}
return 0;
}