请教Snapchat 雷达 这道题

各位大神，看Snapchat的面经，有一道题不太会，不知道各位大神有什么想法
一个tunnel， 范围是[0，1]中间有各种尺寸的雷达，(x, y, r)，一个小车只有不被雷达监测的地方可以通过，问给定一个List<Radar>判断小车能不能过去


http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311

看这个帖子的楼主是用union find， 但是不知道怎么用的，我的想法还是最原始的，把在雷达范围内的点全部标记，然后从最左边的一列找路径到最右边的一列，大家有没有其他方法呀

如果两个圆有overlap就认为联通。如果y=0, y=1和某个圆相交也认为它们联通。
然后就是看y=0, y=1是否在一个connected component里了。如果是的就认为路被block了。

每两个圆心之间求距离，如果距离大于两个半径之和再加一（车的路径）。既可以通过。
小于的话立即返回false。

alucardzhou 发表于 2016-9-15 22:47
每两个圆心之间求距离，如果距离大于两个半径之和再加一（车的路径）。既可以通过。
小于的话立即返回fals ...

这个好像不对吧，假设有一个圆覆盖了路径，但是这个时候也存在一个圆，使他们的距离大于两个半径之和再加上一吧

hxtang 发表于 2016-9-15 20:11
如果两个圆有overlap就认为联通。如果y=0, y=1和某个圆相交也认为它们联通。
然后就是看y=0, y=1是否在一 ...

哦哦，这样，那最后判断是否在一个connected component里面的时候，需要记录每个connected component的x，y的范围吧

神罗天征 发表于 2016-9-16 00:46
哦哦，这样，那最后判断是否在一个connected component里面的时候，需要记录每个connected component的x ...

这个有多种可能实现，纪录x, y是其中一种

神罗天征 发表于 2016-9-15 11:19
这个好像不对吧，假设有一个圆覆盖了路径，但是这个时候也存在一个圆，使他们的距离大于两个半径之和再加 ...

不好意思之前没理解题意，通路原来是指定了的啊。我还以为可以随便开。

Snapchat为什么拒我简历，我心里不平衡

MulinZz 发表于 2016-9-16 03:30
Snapchat为什么拒我简历，我心里不平衡

估计是要上市了，人太多了……好像在招有flag实习的人……

这道题可以这么做：先把所有的雷达处理一遍，把相交的雷达座位一个connected component, 处理完毕后，就会有很多雷达团体，然后判断每个雷达团体的探测最高和最低是否完全跨越了0到1的高度，这些雷达团体的探测范围实际上就是一堆相交的圆，如果这些圆的范围跨越了0->1,那么肯定可以通过圆的内部画一条线出来，挡住0-1,这样就过不去了。只要有一个雷达团体挡住了0-1 那小车就过不去。至于最高和最低 循环处理雷达团体，记录最高和最低值。