Snapchat 雷达探测小车题

[size=14.6667

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

辐射半径)。问你一辆车能否通过这条路。
这个有什么解法

一共n个雷达，初始化为n个集合，每个集合有上界下界两个属性，雷达之间两两比较是否相交，相交的相应集合合并，并且更新上下界。
最后检查是否存在集合上下界完全遮蔽[-1,+1]

（抱歉一个回车就发出去了。。。）

然后顺序查看过去，如下：

for i in 1 .. n:
    if (dis between radar[i].center and radar[i-1].center) <= radar[i].radius + radar[i-1].radius):
        if no space between radar[i] and wall and no space between radar[i-1] and wall:
            return false
return true

这样可行？

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

补充内容 (2016-11-1 02:56):
union find

union find + sweep line吧 虽然还是O(n^2)

linweihua0 发表于 2016-10-20 10:35
union find + sweep line吧 虽然还是O(n^2)

能不能具体说一下，雷达是圆吧，不清楚怎么用line可以做

你可以看看sweeping line algorithm 就是把圆分成左右event

linweihua0 发表于 2016-10-20 10:35
union find + sweep line吧 虽然还是O(n^2)

直觉上应该有 nlogn 的方法 但是想不出来...

oldfish 发表于 2016-11-1 12:13
直觉上应该有 nlogn 的方法 但是想不出来...

感觉不太可能。二维圆相交应该不可能有nlogn的解法。

根据雷达x坐标排序，这样是nlgn。