一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1386|回复: 14
收起左侧

[其他] 请教一道snapchat的小车雷达题

[复制链接] |试试Instant~ |关注本帖
厉害的超人 发表于 2016-9-3 02:39:34 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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

 楼主| 厉害的超人 发表于 2016-9-18 02:21:00 | 显示全部楼层
jy_121 发表于 2016-9-17 08:11
可以想成合并区间吗?

前面czhoume已经给出了解答,重叠的圆圈都group起来,使用union-find就行了。
先给出具体解答,可能有bug,没做深度测试。
  1. #include <map>
  2. #include <vector>
  3. #include <iostream>

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

使用道具 举报

dydcfg 发表于 2016-9-9 03:33:51 | 显示全部楼层
解法应该是用union-find,把所有相交的圆并成一个group,记录group横坐标的最小和最大值[minx,maxx]
然后小车能通过的条件就是没有把路占完的group,也就是所有的[minx,maxx]都是[0,1]的子集.扫一遍判断下就是了.
回复 支持 1 反对 0

使用道具 举报

czhoume 发表于 2016-9-3 06:20:02 来自手机 | 显示全部楼层
本帖最后由 czhoume 于 2016-9-3 06:22 编辑

第一步:一个雷达就是一个圆圈,先过一遍所有的圆圈,把重叠的圆圈都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的数字,就同时重叠路的两边了。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-8 21:58:11 | 显示全部楼层
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)
复制代码
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-8 22:00:24 | 显示全部楼层
... I don't know why all my posted code in previous post got lost...?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-8 22:15:57 | 显示全部楼层
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 }

回复 支持 反对

使用道具 举报

frouds 发表于 2016-9-8 22:43:08 | 显示全部楼层
用sweep line 应该可以
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-9 03:18:02 | 显示全部楼层
可以大概讲一下思路吗? 先sort 所有的 x-r ?
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-9-18 00:11:36 | 显示全部楼层
可以想成合并区间吗?
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-9-18 02:50:13 | 显示全部楼层
厉害的超人 发表于 2016-9-18 02:21
前面czhoume已经给出了解答,重叠的圆圈都group起来,使用union-find就行了。
先给出具体解答,可能有bu ...

感谢回复,我觉得这种做法是没有问题的。我是觉得这题应该也可以用merge interval来解
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-9-18 07:15:27 | 显示全部楼层
jy_121 发表于 2016-9-18 02:50
感谢回复,我觉得这种做法是没有问题的。我是觉得这题应该也可以用merge interval来解

嗯嗯,同感,感觉可以把所有圆y的范围表示成interval,然后merge后,查看是0~1是否全部cover了
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-9-18 07:19:37 | 显示全部楼层
神罗天征 发表于 2016-9-18 07:15
嗯嗯,同感,感觉可以把所有圆y的范围表示成interval,然后merge后,查看是0~1是否全部cover了

想了下还是不能一下merge全部的,总体0-1都覆盖的话还是可以走的
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-9-18 07:49:25 | 显示全部楼层
jy_121 发表于 2016-9-18 07:19
想了下还是不能一下merge全部的,总体0-1都覆盖的话还是可以走的

哦哦,懂了,可能x相差很远,但是y merge了后覆盖0-1对吧,多谢提醒
回复 支持 反对

使用道具 举报

lydxlx 发表于 2016-9-19 09:14:04 | 显示全部楼层
本帖最后由 lydxlx 于 2016-9-19 09:21 编辑

这样做是有问题的。投影过后的区间覆盖[0,1]并不能保证小车一定不能通过
|    ======|
|    ======|
|    ======|
|    ======|
|                 |
|             |
|====       |
|====       |
|====       |
|====       |
|             |
把上面的方块想象成圆即可。


正确做法是反过来考虑,判断小车会不会被堵死。
先建图,每个圆是一个点,路的左右两侧各对应一个点,两圆相交则连边,圆和两侧相交也连边。那么小车会被堵死当且仅当有从左侧到右侧的路径。


回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 15:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表