算法设计沙龙--计算几何问题.doc

个人收集整理 勿做商业用途
算法设计沙龙——-几何算法套餐
福州一中程序设计兴趣小组

　　你了解几何吗?你了解几何算法吗?我们的沙龙将带领你进入几何的世界，进入计算机处理几何问题的领域。先请你思考以下几个问题，试试看你能否解决?

　　一、判断点在多边形中的位置

　　已知点P的X、Y坐标和一个N边形A1A2…An.判断点P在N边形的内部,外部或边上.

　　输入：
　　第1行输入N;
　　第2行至第N+1行输入N边形各点的X、Y坐标；
　　第N+2行输入P点X、Y坐标;

　　输出：
　　如果在内部，输出"NEIBU”
　　如果在外部，输出"WAIBU”
　　如果在边上，输出"BIAN"

二、Car的旅行路线

　　问题描述
　　又到暑假了，住在城市A的Car想和朋友一起去城市B旅游.她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。

　　那么Car应如何安排到城市B的路线才能尽可能的节省花费呢？她发现这并不是一个简单的问题，于是她来向你请教。

　　任务
　　找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。

　　输入文件：键盘输入文件名
　　输　　出：到屏幕（输出最小费用，小数点后保留2位。)

　　输入格式
　　第一行为一个正整数n（0<=n<=10)，表示有n组测试数据。
　　每组的第一行有四个正整数s，t，A，B。
　　S（0〈S〈=100）表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A,B的序号，　　　(1〈=A，B<=S).
　　接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的（xi1，yi1),(xi2,yi2）,(xi3，yi3）分别是第I个城市中任意三个机场的坐标，T I为第I个城市高速铁路单位里程的价格。

　　输出格式
　　共有n行,每行一个数据对应测试数据。

　　样例输入
　　1
　　1 10 1 3
　　1 1 1 3 3 1 30
　　2 5 7 4 5 2 1
　　8 6 8 8 11 6 3

　　样例输出
　　47。55
三、无线电测向

　　问题描述：
　　一艘有天线定位装置的船能通过接收当地灯塔信号来确定自己的位置。每个灯塔固定在已知点上并发出特有的信号。当船检测到信号，它可通过旋转天线直到信号达到最大强度。这样就可确定自身与该灯塔的位置关系。只要接收到两个灯塔的信息，就有可能确定船当前的位置。
　　编程任务：
　　通过一对灯塔信息来确定船的位置。
　　灯塔和船的位置被确定在一个直角坐标系内.X轴正向指向东，Y轴正向指向北。船的航行路线从正北开始按顺时针用度表示。北是0°,东是90°，南是180°，西是270°。灯塔与船的位置关系用相对于船的航行方向顺时针用度表示。

　　数据输入：输入数据由文件名为INPUT.TXT的文本文件提供。文件的第一行是一个整数,表示灯塔的数目N(N<=30)。以下N行,每行表示一个灯塔，为灯塔名称（名称是20个以下的字母）,X坐标和Y坐标。它们都用空格隔开。

　　灯塔信息下面是船的信息包括三行，一行是船的方向，其余两行是所接收到的灯塔信号。
　　具体如下：
　　输入数据　　　　　　　　　　数据的含义
　　方向　 　 　　　　　　　　　船的航行方向；
　　名称１　角度１　　　　　　　第一个灯塔信息的名称，灯塔的方位；
　　名称２　角度２　　　　　　　第二个灯塔信息的名称，灯塔的方位。

　　灯塔的方位为船与灯塔所在的直线与船的航行方向的夹角（从船的航行方向开始顺时针，角度1=角度1+180）。2个数据用空格隔开。

　　数据输出：将船的位置（精确到２位小数）。输出到OUTPUT.TXT文件中。如果无法确定船的位置，应输出"NO ANSWER"（不能使用小写）。

　　输入文件示例
　　5
　　a 1 5
　　b 1 1000
　　c 2 4
　　d 51 60
　　e 153 79
　　30
　　e 160
　　d 210本文为互联网收集，请勿用作商业用途
　　输出
　　160。83 123.41
四、监视摄像机

　　［问题描述］
　　一个著名的仓库管理公司SERKOI请你为其安装一套闭路监视系统，由于SERKOI财力有限，每个房间只能安装一台摄像机，不过其镜头可以向任何方向转换.
　　请你写一个程序，对于给定的房间示意图,判断是否有可能在这个房间中的某一位置安置一台摄像机，使其能监视到房间的每一个角落。

　　[输入格式]
　　第一行是一个整数n（4<=n〈=100）,表示房间的示意图是一个n边形。以下n行，每一行给出一个顶点的坐标（xn，yn）。

　　[输出格式]
　　如果能找出安放摄像机的点则输出’OK！'，否则输出'IMPOSSIBLE！'。

　　［样例］

五、铁路连线问题

　　皮亚琴查是意大利一个美丽的城市，有着丰富的旅游资源.该地的旅游景点又被分为N个自然景观和N个人文景观,为了方便游客，当地政府决定在每两个自然景观和人文景观之间增设一条铁路，也就是增加N条铁路。为了降低工程难度，他们要求铁路之间不能相交，现在你的手边有每个自然景观和人文景观的坐标。市长PIPPO要求你的程序给出一个可行的铁路连线方案.
　　输入:
　　第1行为一个数字N（0<N<10000)；
　　第2N+1行为N个自然景观的坐标，两个数字之间用空格隔开;
　　第N+22N+1行为N个人文景观的坐标，两个数字之间也用空格隔开;
　　输入数据保证有解。

　　输出：
　　输出数据包括N行，为一种可行解的方案。
　　每行包括两个数据，即两个连线的景观的编号。
　　0≤矩形数目<5000；
　　坐标数值为整数，范围是[—10000，10000]。
六、音乐厅布置（Hall.pas/c/cpp）

　　【背景】
　　建成于1891年的纽约卡内基音乐厅（Carnegie Hall）音响效果绝佳,是世界最著名的音乐厅之一，它有很大的舞台,在这个音乐季，他们正准备演出莫扎特（Mozart）的歌剧《后宫诱逃(Die Entfuehrung aus dem Serail）》。剧中某些场景需要搭建一个土耳其皇宫,正如我们所熟悉的阿拉伯建筑风格，"皇宫"由一些高度、直径都相同的圆柱支撑,其中一些柱子和外墙相接，另一些在皇宫内部，所有外墙上的柱子向皇宫内的一侧的地面上都放有灯(假设灯放在柱子的圆心这个点上）,灯光可以照射到皇宫内的任何部分,除非被东西遮挡。”皇宫"外围是灰白色的”石壁”,就是两根柱子中间的部分,并且总在两根柱子圆心的连线上。墙壁都有一定的透光度，使得内部灯光散射出来，晶莹剔透。因为半透明，墙壁不太厚，相对于柱子的直径,我们忽略墙壁的厚度，如右图所示，灰色部分表示皇宫内部，蓝色部分表示柱子内部.皇宫的横截面总是凸多边形,上方有和横截面几何形状一模一样且厚度密度都均匀的平顶（图中线段围住的部分,即以各个外墙上的柱子的圆心为顶点的凸多边形）。演出时场景布置当然要富丽堂皇、尽善尽美，因此他们请天才的你来解决他们的一切问题。

　　【问题】

　　1、 舞台上不能放置太重的东西,柱子、墙壁都是用塑料等轻的材料做的,不能承重。而皇宫的平顶面积大，还是挺重的,不能直接压在这些材料上，只能通过舞台顶部的架子悬挂。当然，悬挂用的绳子是越细越少越好。他们提出一个大胆的想法，让你只用一根非常坚固的绳子，悬挂起整个屋顶。你的任务就是,找到平顶上一个恰当的点，使得从这个点可以把平顶平稳的吊起来.

　　2、 布景时，布景师们在顶部的架子上走动，时常不小心碰到一些工具，掉下去砸坏了道具。因此，他们观察了几个经常放工具的点，并告诉你这些点在舞台上投影的位置,请你判断一下这些东西竖直掉下会对"皇宫"造成什么影响。某物品从某个点落下，如果恰好砸在柱子上（内），输出C；砸到墙壁上，输出L;砸到皇宫内空地，输出I；落到皇宫外，输出O；如果砸到物体的交界处，只需按照CLIO的顺序输出第一个。

　　3、 演出时，录音师为演出制作环绕立体声录音。为了排除墙壁隔音的影响，他们在”皇宫"里的地面上也放置了几个麦克风。但为了不影响灯光照射,麦克风必须放在灯光照射不到的地方。出于声学的考虑,录音师建议了几个适合放置麦克风的位置，请你从光学的角度，分析一下其中那些位置可以放置，哪些不可以。如某个麦克风可以放置,那么输出1，否则输出0。

　　我们用一个平面直角坐标系表示舞台地面,给你的数据包括：柱子总数、直径,”皇宫”高度，平顶厚度,每根柱子中心的坐标，以及问题2、问题3要判断点的坐标.
　　如果你能完美解决了音乐厅面临的三个难题，演出后,你将被授予”最佳协作奖”。

　　【输入】

　　第1行有四个整数,是柱子总数p、直径d、”皇宫”高度h1和平顶厚度h2，数据中间都用一个空格隔开.
　　以下p行，每行有两个实数xi,yi,数据间用一个空格隔开，是第i根柱子的中心坐标。
　　第p+2行是一个整数n,表示问题2要判定的顶点个数。
　　以下n行，每行有两个实数xi，yi，是问题2要判定的第i个点的坐标，数据间用一个空格隔开.
　　第p+n+3行是一个整数m，表示任务3要判定的顶点个数。
　　以下m行，每行有两个实数xi，yi，数据间用一个空格隔开，是任务5要判定的第i个点的坐标，并保证这些点都在”皇宫"的可用空间内。

　　【输出】

　　第1行包含两个实数x，y,表示可以悬挂平顶的点的坐标，数据间用一个空格间隔,保留三位小数。
　　第2行包括n个字母，是CLIO之一，表示问题2的结果，数据间用一个空格间隔。
　　第3行，输出m个数，是0或者1，表示问题3的结构,数字间用一个空格间隔。

　　【样例输入】

　　7 1 110 10
　　—3 3
　　3 2
　　—2 -2
　　3 —1
　　0 0
　　1 1
　　—1 1
　　4
　　-4 1
　　-2 1
　　0 0
　　0 2.5
　　2
　　1 —1
　　0。25 0.75

　　【样例输出】

　　0.015 0.545
　　O I C L
　　0 0 个人收集整理，勿做商业用途
沙龙之《音乐厅布置》解题报告
福州一中 林渌
　　这一题从算法上来说，使比较简单的，只要仔细看清题目的要求，编程细心且耐心，就不难解决问题。

　　首先,求凸包是整个问题的基础，因为题目没有给出哪些柱子是在外，哪些在内，而这将是解决问题必须的条件。求凸包可以用卷包裹法或Graham，我想大家对这应该是很熟悉的了。

　　我们得到凸包之后，很明显可以看出来，第一小题就是求凸包的重心。由于房顶的密度厚度均匀,所以房顶的厚度就是一个不需要考虑的多余条件。求凸多边形重心的一个简单方法就是我们顺次把凸包分割成为n-3个三角心，根据三角形中心的计算公式 就可以得到每个三角形的重心。然后计算三角形面积（如用公式 其中）。这样我们就可以计算两个图形的重心 ,如已知他们的面积（正比于质量）S1，S2，有 ，再利用定比分点公式 求出这两个图形整体的重心（x，y）.

　　这我们可以用很简洁的程序求得：
　　x:=0; y：=0; s：=0；
　　for I:=2 to n—1 do
　　　begin
　　　　x0:=（dian[1］。x+dian［I]。x+dian[I+1］。x）/3;
　　　　y0：=（dian［1]。y+dian［I].y+dian[I+1］。y）/3；
　　　　k：=gets/s; ｛gets为求当前三角形的面积}
　　　　x：=（x+k＊x0）/（1+k）;
　　　　y；=(y+k＊y0）/(1+k）;
　　　　inc(s，gets）;
　　　end;
　　求得的（x，y)即为凸多边形的重心。
　　当然,大家还可以思考一下如果不一定是凸多边形的情况.

　　第二个问题,因为物体是竖直落下，我们实际上要判断的就是物体的射影这个点是在圆内、线上、凸多边形内或者凸多边形外?

　　i） 判断一个点是否在圆内，可以通过计算这个点到圆心的距离，如果距离小于半径那么点就在圆内。
　　这里还要特别注意一点--—--—精度问题
　　对于这里求距离不应该用开平方sqrt ,而应将半径平方,否则会导致精度降低无法求得正确答案

　　ii） 判断一个点是否在线上，可通过下面的方法求得

　　iii) 判断一个点是否在多边形内，只要从这个点向多边形外做一条射线(随机取极远处的一个点,以这两点为端点做一条线段即可），如果射线不经过多边形顶点,不和多边形边重合（随机取点出现这种情况的概率极小，可以不予考虑，或者发现问题马上重新取点），那么统计射线和多边形的边的交点个数，如果是交点是奇数个表明点在多边形内，否则在多边形外.
　　当然对于本题还有另外一种较为简洁的方法:将点与重心连一条线判断这条线是否与凸包的边相交。若相交,则在凸边形外；否则,就在凸多边形内
　　按照上述条件依次判断，也就可以满足本小题CLIO的输出顺序。本文为互联网收集，请勿用作商业用途
　　第三个问题,要判断一个点是否能够被照射到。我们应该看到，麦克风是没有大小的，而且它和灯都是放在地面上，所以皇宫的高度也是一个无用的条件,我们只要考虑平面问题。如果一个点可以防治麦克风，也就是说，它不能够被任何光线照射到，那么这个点和任何灯的连线都会被某一个柱子所遮挡。也就是说，如果一个点和一个光源的连线不被任何柱子遮挡,这个点才是可见的.一盏灯发出去的光线有无数条，根据物理学易知，我们只要考虑灯和麦克风连线上的这一条光线在灯和麦克风之间的线段就可以了.大致算法是我们依次考虑每个麦克风，看它和每根外柱的连线会不会被某根柱子遮挡.这样算法的时间复杂度为 。关键就是如何判断线段和圆相交，其实有多种可行的方法。标程使用了的方法是计算出线段所在直线和圆的交点，判断焦点是否在线段上。这种方法简单易懂容易想到，只要利用解析几何知识认真笔算一下直线和圆的交点就行了。我的方法是判断圆心到直线的距离及交点，如果相交的话再判断线段的两个端点是否分列在圆心到直线的垂线的两侧.其他方法还有很多,这里就不再介绍了.

　　至此这样整道题目就解决了，当然计算几何的很多基本算法都可以有不同的实现方法。这道题没有复杂的思想，主要是套用常见的计算几何算法。

　　参考程序

　　 　文档为个人收集整理，来源于网络
沙龙之《铁路连线问题》解题报告
福州一中 严寒凝
[解题思路］

　　本题是一道简单的几何算法和分治策略相结合的题目.
　　我们先用与Graham扫描法相类似的方法对于题目给出的点进行顺时针或逆时针排序,然后找出一点y坐标值最低的点记为V1,按顺序扫描这些点，累加所扫描到的人文景观和自然景观的个数，（注意：V1也要统计在内)，直到扫描到的一点Vj,使人文景观和自然景观的个数相等，恰好可以与V1相搭配，我们就在V1，Vj之间建立一条铁路连先，这样原本排好序的集合（V1,V2…………VN）就可以化为两个更小的集合（V2……Vj-1）和（Vj+1……Vn），可以递归的求解。