[其他] 猜谜！

班超

波恩大学某系办公楼的平面图是不规则的多边形，多边形内部无障碍。
如果要在楼里安装摄像头监视该平面内所有地方，无论这个多边形多复杂，安几个摄像头肯定够用？？？

[ 本帖最后由 班超 于 2006-12-20 08:37 编辑 ]

班超

原帖由 iatb 于 2006-12-19 20:07 发表
摄像头能拍摄多大角度

自然是360。

班超

原帖由 dongfeng71 于 2006-12-19 21:54 发表


那就太简单了。 在该多边形围成的区域内的不在任何边上的任意一点放置 都可以。

这是任意多边形，有些内凹的边角会对视线构成阻挡的。

[ 本帖最后由 班超 于 2006-12-20 08:37 编辑 ]

班超

原帖由 qquchn 于 2006-12-20 00:19 发表
放置摄像头使要监控每一个角落么？就是说摄像头要看到每一个地方么？

OF COURSE! PLEASE CONTINUE.

班超

摄像头当然是上下左右都可以看到，所以角度问题与此题无关。

但请注意和人一样它的视线不能拐弯，所以有些墙体会挡住它的视线，看不到挡在后面的区域。
因此我们考虑多边形的任意形状这点就够了，纯粹是平面问题。

[ 本帖最后由 班超 于 2006-12-20 12:07 编辑 ]

班超

原帖由 seefilm 于 2006-12-20 14:52 发表
肯定有解吗？如果楼房横剖面是这种螺旋状的，似乎螺旋匝数越多，需要的摄像头就越多。

或者在所有拐角处按个反光镜，只要角度调整好，那么一个摄像头就够了

说过了，是多边形，封闭的，你画的黑色部分算是。

[ 本帖最后由 班超 于 2006-12-20 16:28 编辑 ]

班超

原帖由 seefilm 于 2006-12-20 15:56 发表
这个也算

这几个黑色部分都是多边形，没问题。

班超

原帖由 chinesehejing 于 2006-12-20 18:33 发表
n/2或n/2+1

接近了。

班超

原帖由 qquchn 于 2006-12-20 21:20 发表
你的题目是至少多少摄像头，而n/2肯定不是最优解 这只是最坏情况下的解 还应当给出约束 如果平面图只有矩形 则N/4 下取整

你的思路加上楼上的思路就差不多了，现在只缺一个答案！

班超

n/3 beschränk nach unten