人在德国社区 - Powered by Discuz! Board

标题: [其他] 猜谜！ [打印本页]

作者: 班超 时间: 2006-12-19 19:08 标题: 猜谜！

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

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

作者: iatb 时间: 2006-12-19 20:07

摄像头能拍摄多大角度

作者: dongfeng71 时间: 2006-12-19 21:27

好题，有点儿难度！

但是条件明显不足。

作者: 班超 时间: 2006-12-19 21:42 标题: 哦

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

自然是360。

作者: dongfeng71 时间: 2006-12-19 21:54

原帖由班超于 2006-12-19 21:42 发表

自然是360。

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

作者: 班超 时间: 2006-12-19 23:41 标题: no

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

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

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

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

作者: Klein_Yu 时间: 2006-12-20 00:07

一个啦。
不管是不是不规则的多边形，因为，多边形内部无障碍。
所以，要在楼里要安装监视摄像头，只要把摄像头挂起来，就都覆盖得到了。

[ 本帖最后由 Klein_Yu 于 2006-12-20 00:23 编辑 ]

作者: qquchn 时间: 2006-12-20 00:19

放置摄像头使要监控每一个角落么？就是说摄像头要看到每一个地方么？

作者: 班超 时间: 2006-12-20 08:36 标题: o

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

OF COURSE! PLEASE CONTINUE.

作者: seefilm 时间: 2006-12-20 10:19

提示: 作者被禁止或删除内容自动屏蔽

作者: qquchn 时间: 2006-12-20 10:36

把这个不规则多边形切成若干个正方形区域，每个正方形中心放置摄像头

作者: 班超 时间: 2006-12-20 11:57 标题: 哦

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

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

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

作者: seefilm 时间: 2006-12-20 14:52

提示: 作者被禁止或删除内容自动屏蔽

作者: 班超 时间: 2006-12-20 15:35 标题: o

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

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

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

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

作者: seefilm 时间: 2006-12-20 15:49

提示: 作者被禁止或删除内容自动屏蔽

作者: seefilm 时间: 2006-12-20 15:55

提示: 作者被禁止或删除内容自动屏蔽

作者: seefilm 时间: 2006-12-20 15:56

提示: 作者被禁止或删除内容自动屏蔽

作者: 班超 时间: 2006-12-20 16:27 标题: dui

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

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

作者: qquchn 时间: 2006-12-20 18:15

你这些都是矩形组成的如果有三角形的话问题就变得复杂了因为入射角度很重要

作者: chinesehejing 时间: 2006-12-20 18:33

n/2或n/2+1

作者: qquchn 时间: 2006-12-20 19:24

你这个答案有点不靠谱

作者: 班超 时间: 2006-12-20 20:43 标题: en

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

接近了。

作者: qquchn 时间: 2006-12-20 21:20

你的题目是至少多少摄像头，而n/2肯定不是最优解这只是最坏情况下的解还应当给出约束如果平面图只有矩形则N/4 下取整

作者: 班超 时间: 2006-12-20 22:00 标题: ha

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

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

作者: dongfeng71 时间: 2006-12-20 23:38

快给答案，快给答案！

作者: 班超 时间: 2006-12-21 17:03 标题: ok

n/3 beschränk nach unten

作者: qquchn 时间: 2006-12-21 22:27

你这是最坏情况还是平均？

作者: 班超 时间: 2006-12-21 23:17 标题: 哦

原帖由 qquchn 于 2006-12-21 22:27 发表
你这是最坏情况还是平均？

Fuer Ein einfaches Polygon mit n Ecken kommen stets n/3 (beschraekt nach unten) Waechter aus.

作者: Klein_Yu 时间: 2006-12-25 00:22

答案好像有点问题哦！如果是一个正六边形，只要在中心点放置一个摄像头就可以了。那么，n/3就好象不对了。

欢迎光临人在德国社区 (http://csuchen.de/bbs/)