z****h
发帖数: 164 | 1 16. [Microsft] 给出平面上第一象限内landscape 的轮廓，也就是一些列的(x,y)坐标
, x=0,1,...,N
，以及Y 轴上光源坐标(0,H)。问这N+1 个点钟那些被照亮那些是阴影。(叉乘)
一一计算光源到(x,y)的角度，再与左边的角度对比即可知是否被遮挡，复杂度O(N)
只需要与左边角度对比？O(N)?
我还是觉得必须n方阿。
哪位大牛指点一下？谢谢！ | l*****a
发帖数: 14598 | 2 我认为
每个点跟之前的极值点比较即可
所以是线性
【在 z****h 的大作中提到】
: 16. [Microsft] 给出平面上第一象限内landscape 的轮廓，也就是一些列的(x,y)坐标
: , x=0,1,...,N
: ，以及Y 轴上光源坐标(0,H)。问这N+1 个点钟那些被照亮那些是阴影。(叉乘)
: 一一计算光源到(x,y)的角度，再与左边的角度对比即可知是否被遮挡，复杂度O(N)
: 只需要与左边角度对比？O(N)?
: 我还是觉得必须n方阿。
: 哪位大牛指点一下？谢谢！
| z****h
发帖数: 164 | | l*****a
发帖数: 14598 | 4 (0,h) 与 (x,y)的角度/斜率。。
【在 l*****a 的大作中提到】
: 我认为
: 每个点跟之前的极值点比较即可
: 所以是线性
| p*****2
发帖数: 21240 | | m*****g
发帖数: 226 | 6 blockedPoints = []
for point in points:
angle = getAngle(point, lightOrig)
allAngles[angle]++;
if allAngles[angle] > 1 :
blockedPoints += points
【在 z****h 的大作中提到】
: 16. [Microsft] 给出平面上第一象限内landscape 的轮廓，也就是一些列的(x,y)坐标
: , x=0,1,...,N
: ，以及Y 轴上光源坐标(0,H)。问这N+1 个点钟那些被照亮那些是阴影。(叉乘)
: 一一计算光源到(x,y)的角度，再与左边的角度对比即可知是否被遮挡，复杂度O(N)
: 只需要与左边角度对比？O(N)?
: 我还是觉得必须n方阿。
: 哪位大牛指点一下？谢谢！
| A**l
发帖数: 2650 | 7 我连题目都没看懂，到底是N+1个“点”互相遮挡，还是这些点形成的多边形遮挡
另外这些点给出来的顺序也很重要，从左到右、从上到下顺时针、逆时针。。。
不过基本上是计算几何的问题
【在 z****h 的大作中提到】
: 16. [Microsft] 给出平面上第一象限内landscape 的轮廓，也就是一些列的(x,y)坐标
: , x=0,1,...,N
: ，以及Y 轴上光源坐标(0,H)。问这N+1 个点钟那些被照亮那些是阴影。(叉乘)
: 一一计算光源到(x,y)的角度，再与左边的角度对比即可知是否被遮挡，复杂度O(N)
: 只需要与左边角度对比？O(N)?
: 我还是觉得必须n方阿。
: 哪位大牛指点一下？谢谢！
| G******e
发帖数: 229 | | z****h
发帖数: 164 | 9 多谢，这是空间换时间吧。
space O(n), time O(n).
不过从原作者描述好像是有space O(1) time O(n)的解法。。。
【在 m*****g 的大作中提到】
: blockedPoints = []
: for point in points:
: angle = getAngle(point, lightOrig)
: allAngles[angle]++;
: if allAngles[angle] > 1 :
: blockedPoints += points
| z****h
发帖数: 164 | 10 confused.不能只跟之前的极值比吧。比如 X1 (1,h), X2(3, h), .... Xi-1(49, h)
Xi(50,h)。Xi不会被Xi-1遮挡但是会被不相临的x1遮挡。
【在 l*****a 的大作中提到】
: 我认为
: 每个点跟之前的极值点比较即可
: 所以是线性
| | | z****h
发帖数: 164 | 11 我是这样理解的。假设每个点都是一个物理点的实体，在光源照射后都有阴影，而且阴
影就是一条直线。如果有两个点和光源在一条直线上，离光源近的点被照亮，后面的点
被遮挡。比如光源在(0,h), x1( 1, h), x2(2, h)，x1被照亮，x2被遮挡。
【在 p*****2 的大作中提到】
: 没看明白。几何的东西？
| I*******l
发帖数: 203 | 12 If all the points are already sorted based on x-coordinate, then O(n) time
should be enough. Otherwise you need O(nlogn) time to first sort these
points and then process the n points from left to right and use a hash table
to store the blocked (or shadowed) angles.
【在 z****h 的大作中提到】
: 我是这样理解的。假设每个点都是一个物理点的实体，在光源照射后都有阴影，而且阴
: 影就是一条直线。如果有两个点和光源在一条直线上，离光源近的点被照亮，后面的点
: 被遮挡。比如光源在(0,h), x1( 1, h), x2(2, h)，x1被照亮，x2被遮挡。
| z****h
发帖数: 164 | 13 就算按x排序了也不行吧。
光源(0,h), x1( 1, h), x2 ( 2, 1) .... xn (n, h)
x1会挡xn
table
【在 I*******l 的大作中提到】
: If all the points are already sorted based on x-coordinate, then O(n) time
: should be enough. Otherwise you need O(nlogn) time to first sort these
: points and then process the n points from left to right and use a hash table
: to store the blocked (or shadowed) angles.
| I*******l
发帖数: 203 | 14 In this case, after processing x1, slope k=0 will be stored in the hash
table. Then xn knows it will be blocked.
【在 z****h 的大作中提到】
: 就算按x排序了也不行吧。
: 光源(0,h), x1( 1, h), x2 ( 2, 1) .... xn (n, h)
: x1会挡xn
:
: table
| y****g
发帖数: 5 | 15 只需用一个变量记录之前点中的最高点，每次与这个最高点比较即可。算法其余的部分
与楼主的想法一样。这样的复杂度是O（n）。 |
|
