请教一道snapchat的小车雷达题

题目：一个路，路两边可以想象为 y = 0 和y = 1两条直线，中间有各种尺寸的雷达，(x, y, r)，r为探测范围，一个小车只有不被雷达监测的地方可以通过，问给定一个List<Radar>判断小车能不能过去。

没啥思路，有人说用union find做。有人说建一个matrix，然后把雷达覆盖的范围都用1表示，然后就是bfs，但这个题貌似x,y都是浮点数，怎么建matrix呢。

解法应该是用union-find,把所有相交的圆并成一个group,记录group横坐标的最小和最大值[minx,maxx]
然后小车能通过的条件就是没有把路占完的group,也就是所有的[minx,maxx]都是[0,1]的子集.扫一遍判断下就是了.

jy_121 发表于 2016-9-17 08:11
可以想成合并区间吗？

前面czhoume已经给出了解答，重叠的圆圈都group起来，使用union-find就行了。
先给出具体解答，可能有bug，没做深度测试。

1. #include <map>
   
2. #include <vector>
   
3. #include <iostream>
   
4. 
   
5. using namespace std;
   
6. struct Radar {
   
7.     double x, y, r;
   
8.     Radar(double _x, double _y, double _r):x(_x),y(_y),r(_r){}
   
9. };
   
10. struct UF {
    
11.     vector<int> parent;
    
12.     UF(int n) {
    
13.         parent=vector<int>(n,-1);
    
14.     }
    
15.     int findRoot(int i) {
    
16.         if(parent[i]==-1) return i;
    
17.         parent[i]=findRoot(parent[i]);
    
18.         return parent[i];
    
19.     }
    
20.     void unite(int i, int j) {
    
21.         int iroot=findRoot(i), jroot=findRoot(j);
    
22.         if(iroot!=jroot) parent[jroot]=iroot;
    
23.     }
    
24. };
    
25. bool radarCar(vector<Radar> &radars) {
    
26.     int n=radars.size();
    
27.     UF uf(n);
    
28.     for(int i=0; i<n-1; ++i) {
    
29.         for(int j=i+1; j<n; ++j) {
    
30.             double rr=radars[i].r+radars[j].r;
    
31.             double dx=radars[i].x-radars[j].x;
    
32.             double dy=radars[i].y-radars[j].y;
    
33.             if(rr*rr>=dx*dx+dy*dy) uf.unite(i,j);
    
34.         }
    
35.     }
    
36.     map<int,vector<int>> groups;
    
37.     for(int i=0; i<n; ++i) {
    
38.         groups[uf.findRoot(i)].push_back(i);
    
39.     }
    
40.     for(auto & e:groups) {
    
41.         double down=1, up=0;
    
42.         for(int idx:e.second) {
    
43.             up=max(up,radars[idx].y+radars[idx].r);
    
44.             down=min(down,radars[idx].y-radars[idx].r);
    
45.         }
    
46.         cout << "up: " << up << ", down: " << down << endl;
    
47.         if(up>=1 && down <=0) return false;
    
48.     }
    
49.     return true;
    
50. }
    
51. int main() {
    
52.     vector<Radar> radars;
    
53.     radars.push_back(Radar(1,0.8,0.6));
    
54.     radars.push_back(Radar(2,0.2,0.2));
    
55.     radars.push_back(Radar(1.5,0.5,0.3));
    
56.     radars.push_back(Radar(2,1.2,0.65));
    
57.     cout << "Can pass? " << radarCar(radars) << endl;
    
58. }
    

复制代码

第一步：一个雷达就是一个圆圈，先过一遍所有的圆圈，把重叠的圆圈都group起来（大圈包小圈算重叠），比如你有四个圈，1号圈独立，2和3重叠，3和4重叠，那你就有两个group，1是一个，234是一个. group的方法我没想到很好的，也许有现成的算法我不知道。我的想法是把所有的点按照y的值sort，然后将每个点圆心和其他圆心比较距离是否小于半径加和（只需比较两个圆心垂直距离就是y1-y2小于2的，因为如果大于2的话这两个圆有一个就可以把整个路赌了）  
第二步：过一遍所有的group，检查这个group是否和路的两边重叠。如果两边都重叠直接返回无法通过，如果不都重叠检查下一个group.直到检查完所有的group. 具体检查一个group是否和路的两边的做法是：一个group有n个圈，通过每一个圈产生两个数字，x+r和x-r，如果2n个数字中同时有大于1和小于0的数字，就同时重叠路的两边了。

czhoume had a good idea to group radars first. However, I didn't quite get "y1-y2" and ">2" parts. Anyway, here is my code roughly based on czhoume's idea. Sorry the indentation in code might be offset as I still start to get used to post in this forum.
Define struct Radar for convenience:

1. struct Radar {
   
2. double x, y, r;
   
3. Radar(double xx, double yy, double rr) : x(xx), y(yy), r(rr) {};
   
4. };

复制代码

Implement function to group connecting radars. Note: these are arbitrary circles with full degree of freedom, so I think the algorithm has to be O(N^2) because the connectivity between a pair of circles is totally independent. Any better idea?

1. // group radar set into set of radar sets such that each set has connected radars and different
   
2. // sets have no connection

复制代码

Now we can check whether the car can pass from far left to far right without being detected by radars. Note: the car can pass if and only if no group of connected radars can block entire range of [ymin, ymax].

1. bool Pass (set& rds, double ymin = 0.0, double ymax = 1.0)

复制代码

... I don't know why all my posted code in previous post got lost...?

Sorry I have to re-paste my post without indentation. Sorry for the inconvenience.
czhoume had a good idea to group radars first. However, I didn't quite get "??????????????y1-y2??2?,??????2??????????????????" . Anyway, here is my code roughly based on czhoume's idea.

Define struct Radar for convenience:
struct Radar { double x, y, r; Radar(double xx, double yy, double rr) : x(xx), y(yy), r(rr) {}; };

Implement function to group connecting radars. Note: these are arbitrary circles with full degree of freedom, so I think the algorithm has to be O(N^2) because the connectivity between a pair of circles is totally independent. Any better idea?
// group radar set into set of radar sets such that each set has connected radars and different // sets have no connection set> group(set& rds) { set> gps; for (auto& rd:rds) { set s; s.insert(rd); for (auto& gp:gps) { if (connect(gp, rd)) { s.insert(gp.begin(), gp.end()); gps.erase(gp); } } gps.insert(s); } return gps; }
// check if radar set "rds" is connected with radar "rd" bool connect(set& rds, Radar& rd) { for (auto& x:rds) if (connect(x,rd)) return true; return false; }
// check if two radars connect bool connect(Radar& rd1, Radar& rd2) { double center_diff = (rd1.x-rd2.x)*(rd1.x-rd2.x) + (rd1.y-rd2.y)*(rd1.y-rd2.y); double radius_sum = (rd1.r + rd2.r)*(rd1.r + rd2.r); return center_diff <= radius_sum; }

Now we can check whether the car can pass from far left to far right without being detected by radars. Note: the car can pass if and only if no group of connected radars can block entire range of [ymin, ymax].

bool Pass (set& rds, double ymin = 0.0, double ymax = 1.0) { set> gps = group(rds); for (auto& gp : gps) { bool reachMin = false, reachMax = false; for (auto& rd:gp) { if (rd.y+rd.r >= ymax) reachMax = true; if (rd.y-rd.r <= ymin) reachMin = true; if (reachMax && reachMin) return false; // group "gp" blocks the pass } } return true; // no group can block the pass }

用sweep line 应该可以

可以大概讲一下思路吗？ 先sort 所有的 x-r ?

可以想成合并区间吗？