寒，修玛进了奥林匹克竞赛试题
但愿没火星山东省2005年信息学奥赛选拔赛第三试试题
4.屠龙传说-屠龙枪卷(dragon.PAS)
先知看到修玛取回的药草，满意地点了点头。他对修玛说：“跟我来”。修玛顺从地跟着先知走到了他的房间里。先知的房间很大，四周满是书架，整整齐齐地摆放着一排排书籍。房间中间的圆桌上摆放着一个巨大的水晶球，它发出的荧光照亮了整个房间。先知走到一排书架前，从中抽出一本薄薄的书来。这本书看起来十分古老，纸张都变成了黄色，有的地方已经发黑。修玛想，这本书的历史大概有好几百年了吧。先知示意修玛坐下，他翻开手中的书，对修玛说道：“我已经研究这本书很久了。它是用一种古老的文字写成的，记载了一个十分古老的传说。书中提到，普通的武器是无法伤害巨龙的，只有诸神合力锻造的屠龙枪才能消灭它。为了防止屠龙枪被滥用，神把它封印在卡基思山上，只有拥有超人的勇气、力量和智慧的人才能解开这个封印。千百年来，很多人都想得到屠龙枪的力量，然而从没有人成功过。我查阅了所有有关屠龙枪的记载，悉心地研究那些资料，得知屠龙枪被封印在山顶的神殿中，而要解开这道封印，就必须把神殿中的一块巨大的圆石推到神殿祭坛的中心，然后念出解开封印的咒语。”修玛问道：“那句咒语应该已经失传了吧？”“不，恰恰相反。”先知说，“这句咒语一直记载在这本书中，并被完好地保存下来。”“那么，剩下的只是把圆石推到祭坛的中心了。”修玛自信地笑了。然而先知却摇了摇头，“不，修玛，事情没有你想象的那么简单。爬上卡基思山就不是一件容易的事。它高耸入云，四周都是光秃秃的石壁，几乎没有落脚的地方。只有真正的勇士才能爬得上去。那块圆石也不是那么容易就能推动的，非得有超常的力量不可。这些东西，修玛你都有。但如果仅仅只有这些，那么屠龙枪早已被人拿到手了。书中不是说了么，要有勇气、力量和智慧。智慧才是真正的关键。如果在固定时间内不能把那块圆石推到祭坛的中心，那么圆石便会自动滚回原处，同时推石的人将永远无法再次推动这块圆石。而且不管你用多大力气推，这块圆石都不可能滚动得像你希望的那样快，我估计只有按照最短路线去推这块圆石，才能在固定时间内把它推到祭坛中心。神殿中又有着大大小小的石柱，有些石柱与石柱之间的空隙很小，根本就推不过去。正因为这种种困难，才没有人能够从神殿中取走屠龙枪。”修玛沉默了一会儿，说：“不管如何，我也要去试一试。如果我不能拿到屠龙枪，就没有人能够拿到它了。”先知点了点头，说：“去吧，修玛。记住，用你的智慧。”
修玛骑马奔驰了十天十夜，终于来到了卡基思山脚下。正如先知所说的那样，这座山根本就没有路可以上去，甚至找不到可以落脚的地方。然而修玛凭着他的勇气以及熟练的技巧，爬上了山顶。他走进神殿，一眼就看到了那块巨大的圆石。修玛该怎么做，才能把圆石推到祭坛的中心呢？
任务：
你的任务是计算出把圆石推到祭坛中心的最短路线长度。所谓推到祭坛中心是指圆石的中心与祭坛中心重合。圆石中心的初始位置以及祭坛中心的位置是已知的。圆石半径为R，它可以朝着任意方向滚动。洞中所有石柱均为正四棱柱，大小不一。在推动圆石的过程中，要求圆石中心与所有石柱的距离均不小于R，否则圆石将被石柱阻挡而不能继续滚动。
输入(dragon.in)：
输入文件dragon.in第一行包含了五个实数，依次表示圆石中心的初始位置的x坐标、y坐标、圆石半径R、祭坛中心的位置的x坐标以及y坐标。第二行包含一个整数N（0<=N<=20），表示神殿中石柱的数目。接下去N行每行包含三个实数，给出了一根石柱的信息。第I+2行的三个实数依次表示第I根石柱左下角x坐标、y坐标以及该石柱的边长。所有实数均精确到2位小数，范围在0到1000之内。
输出(dragon.out)：
输出文件dragon.out仅包含一个实数表示把圆石推到祭坛中心的最短路线长度，输出结果保留到两位小数。你可以假设总存在一条把圆石推到祭坛中心的路。
输入样例(dragon.in)：
0 0 10 30 40
1
10 10 10
输出样例(dragon.out)：
57．93
修玛思索良久，果断地走到圆石旁边，用力推动这块巨石。圆石在修玛的推动下，缓缓地滚动起来。修玛时不时地调整着推动的角度，以使巨石朝着自己希望的方向滚动。终于，“卡嗒”的一声，圆石安安稳稳地滚到了祭坛的中心。一束光从神殿顶上直射而下，笼罩了整个祭坛。修玛对着祭坛，大声地念出了解开封印的咒语。顿时，祭坛开始颤动，中间的圆石也随着摇摆不定。突然间，整块圆石完全爆裂开来，在祭坛的中心，出现了一柄长枪。枪身上闪烁着神圣的光芒，令人惊羡不已。修玛走上前去，拔起了这柄枪。他感到一股强大的力量从手上传了过来。修玛随手把枪一挥，只听得“哗啦”一声，一根巨大的石柱应声四分五裂了。修玛又惊又喜，他知道这一定就是屠龙枪。 请受我一拜……[s:19] 拜这位老师。。。。。不知道是否在这里潜水阿 [s:19] 原来修玛大人是这么强悍的。。。。。。 e ~~~~~ 见见这个老师 和他商量下 是否让偶们家小雷也上到题目呢？？？
要求八高 出道魔法药量计算好来！！！ 好……强……请允许我膜拜一下 [quote]信息学奥赛[/quote]
太正常了……太正常了……如果是搞信息学的便经常可以见到此类的东西呀……
恩……
上线找那边的同学联系了下，貌似出题那人我还见过，xd 拜啊。。。。五体投地了。。。。果然够强。。。 在下的那届另一个竞赛里出现《星际迷航记》电影第四话里 Excelacor 追 Enterprise-A 滴场景题…… 让GRE阅读理解这种粗浅的东西去败吧……这帖才是王道…… OIBH上有NAXX的 修玛?
BSBSBSBSBS- -|| 改一下就是数学题了……等我以后混到能命中考题，一定出老崔……
老崔第一秒出2刀砍死6个地精，第5秒出10刀砍死5个地精，第15秒出30刀砍死了35个地精……
请判断一下老崔第n秒出几刀砍死多少地精…… 修玛同志实在是太强了....一定有银龙的祝福(INT+18) [s:19] [quote][b]引用第12楼[i]miragesv[/i]于[i]2007-04-09 13:41[/i]发表的“”[/b]:
改一下就是数学题了……等我以后混到能命中考题，一定出老崔……
老崔第一秒出2刀砍死6个地精，第5秒出10刀砍死5个地精，第15秒出30刀砍死了35个地精……
请判断一下老崔第n秒出几刀砍死多少地精……[/quote]
这样会有其他学科的老师们纷纷跳出来抗议的 没有人关心题本身么？
偶的解法一：
假设1：山头近似认为是平直平面
假设2：路径不存在跳跃点
假设3：圆柱不存在重叠
首先建立单点节点列表:
public class Node
{
public Point current;
public Point last;
public float currentDistanceToAltar;
public float currentRouteDistance = 0.0f;
}
List<Node> nodesInCurrentLayer = new LinkedList<Node> ();
List<Node> nodesInNextLayer = new LinkedList<Node> ();
读出所有圆柱坐标，以圆柱中心为中心，半径为圆柱本体半径+球半径，建立圆形障碍列表
将问题从一个圆形与很多圆形看成一个点与很多圆形的问题
public class Obstacle
{
public Point position;
public int radius;
}
public List<Obstacle> obstacles = new LinkedList<Obstacle>;
计算起点到终点的直线距离，构建起点节点对象，将起点节点加入当前层节点列表，线路距离为0，上层点为空；
对于当前层列表中的所有节点，求到所有障碍的外切点（每个两个切点），共40个，加上祭坛位置共41个点；
如果当前节点中上层节点对象不为空且上层节点==目标节点，去掉（不走回头路）；
如果目标节点到祭坛的位置比当前节点到祭坛的位置远，去掉（圆形是凸形，不存在路径奇点）；
从起点连上所有点组成线段，检查所有圆柱与线段是否有交点（点线距离公式+端点距离判断），如有交点，去掉；
将其余线段端点构造节点对象，存入下层节点列表，同时对这些点记录上次经过的节点(Node.lastPoint)，将线段长度累计到总路径距离(Node.currentRouteDistance)上去；
清空当前层节点列表，将下层节点列表复制到当前层节点列表中来
本层节点列表中是否存在终点节点？Y->结束,N->GOTO 2
输出距离到dragon.out
完毕
偶的解法二：
修玛同志一个“律令：统统都给我轰飞口牙”把此山夷为平地，
于是最小距离=球到祭坛的直线距离
其实我就是来秀解法二的…… 楼上分析得很好，只是洞中所有石柱均为[i][u]正四棱柱[/u][/i]，障碍的计算会更复杂 凯特林：提利昂干的
提利昂：提培尔干的
提培尔：不是我干的
乔弗里：不是我干的
经调查证实，四人中只有一个人说的是真话。
问：谁干的？ 没见着是四棱柱，不过这样只是把切点变成4个交点，反而简单了
或者根据棱柱分布建立Tile表直接标准A*也可以，不知道这个无聊竞赛允许不允许塞GPL代码进去……
不过我还是觉得解法2好~~ [quote][b]引用第17楼[i]Gellidus[/i]于[i]2007-04-09 23:56[/i]发表的“”[/b]:
凯特林：提利昂干的
提利昂：提培尔干的
提培尔：不是我干的
.......[/quote]
如果你要说这四个人里只有陪提尔说的是真话，我真是打死都不能信阿~~~ [quote][b]引用第17楼[i]Gellidus[/i]于[i]2007-04-09 23:56[/i]发表的“”[/b]:
凯特林：提利昂干的
提利昂：提培尔干的
提培尔：不是我干的
.......[/quote]
乔佛里干的 修玛传奇么？据说这书不是太好看 不是“不太好看”，而是“太不好看”…… 回18楼：
由于修玛推动的是圆球，而圆球延直角滚动的时候走的是弧线，所以不能简单的看成4个交点。把圆球视为一个点的时候，相应的，要把直角四棱柱的边界以圆球半径R进行膨胀，变为圆角四棱柱。因此每个障碍需要考虑4个切点。
还有，这道题所有的坐标和边长都是实数，无法转换为Tile。
A*算法如果启发函数选得不好，就不一定能得到最优解。这道题障碍不会大于20，广度优先就足够了。
解题思路应该是建立所有可能路径的路径表，然后使用广度优先搜索。
PS：要是修玛真的能做到解法2，那他赤手空拳也能打扁一条龙了 ；） 每个石柱要计算两个切点，还要计算演四分之一圆弧滑动的距离
真是个口胡竞赛…… 这种题还是凭直觉做吧……一看就眼花。修马肯定是先喝了一瓶暴风巨人巨力药水然后推圆球滚直线距离把石柱全撞断过去的 <p>这帖子果然是可怕的东西……</p><p>不过我认为修马一定使用了第三种方法<br />“亲爱的，帮我把那个石头球放到祭坛中心去好么？”<br />“小菜一碟，honey~”</p> -_-这真的不是在恶搞？ 我已然无语了，疯狂的世界。 这个让我想起了某期杂文选刊中某篇文章的某道数学题：
[b][i]唐代大诗人李白曾经写过一首诗，“朝辞白帝彩云间，千里江陵一日还。两岸猿声啼不住，轻舟已过万重山。”请根据此诗，算一算舟船行驶的速度。[/i][/b] 妖精我完全无语了…………真是有创造力的东东………… [quote][b]引用第14楼[i]askask[/i]于[i]2007-04-09 18:27[/i]发表的“”[/b]:
这样会有其他学科的老师们纷纷跳出来抗议的[/quote]
他们为什么要跳出来，他们又不是地精……
[quote][b]引用第23楼[i]Gellidus[/i]于[i]2007-04-10 15:56[/i]发表的“”[/b]:
回18楼：
由于修玛推动的是圆球，而圆球延直角滚动的时候走的是弧线，所以不能简单的看成4个交点。把圆球视为一个点的时候，相应的，要把直角四棱柱的边界以圆球半径R进行膨胀，变为圆角四棱柱。因此每个障碍需要考虑4个切点。
还有，这道题所有的坐标和边长都是实数，无法转换为Tile。
A*算法如果启发函数选得不好，就不一定能得到最优解。这道题障碍不会大于20，广度优先就足够了。
.......[/quote]
能否采用广度优先我还没想清楚，不过列出所有可能路径恐怕……这不是迷宫问题，地图不是一格一格的，而是实数，虽然只精确到小数点后2位，但是1000的最大值设定……1000/0.01=100,000，这还只是一个维度。
PS:虽然转弯半径有个最小值，但是没有说一定要以这个半径转弯啊，而且每次也不一定正好转过1/4个圆弧，最简单的，圆石到祭坛中心的直线上只有1个石柱，而且此石柱的直径跟此直线重合，这样就要转1个直角弯和2个45度弯。所以我觉得这道题更偏向数学题目，而不是计算机题目
刚才又从新想了一下，转弯确实应该以圆石半径转的，不然肯定不是最小距离，但是仍然不一定每次都转过1/4个圆周，这样的话，每个障碍物就不只是4个切点了……
又PS:
最小值是0.01而最大值是1000的话……我们可以认为单位是码，1000码的石柱已经很粗了，然则如果圆石足够大，只要在祭坛中心周围围一圈边长0.01码（约等于9毫米）的石柱就能阻止我们的屠龙英雄拯救世界 [s:8] 地精为什么要跳出来,地精又不是修玛.......... [quote][b]引用第31楼[i]KOU_ZX[/i]于[i]2007-04-11 13:23[/i]发表的“”[/b]:
他们为什么要跳出来，他们又不是地精……
.......[/quote]
因为这个题目出的让物理老师和生物老师等等都很没有面子。。。。。 [quote][b]引用第32楼[i]正直鱼[/i]于[i]2007-04-11 13:27[/i]发表的“”[/b]:
地精为什么要跳出来,地精又不是修玛..........[/quote]
修玛为什么要跳出来，修玛又不用考试 考试为什么要跳出来，考试又不是兔子．．．．．．．．．． 兔子为什么要跳出来，兔子又……（小雷插话：因为这里是我的地盘，我的地盘听我的） [s:34] 小雷为什么要跳出来，小雷又不是周杰伦 [quote][b]引用第31楼[i]KOU_ZX[/i]于[i]2007-04-11 13:23[/i]发表的“”[/b]:
能否采用广度优先我还没想清楚，不过列出所有可能路径恐怕……这不是迷宫问题，地图不是一格一格的，而是实数，虽然只精确到小数点后2位，但是1000的最大值设定……1000/0.01=100,000，这还只是一个维度。
PS:虽然转弯半径有个最小值，但是没有说一定要以这个半径转弯啊，而且每次也不一定正好转过1/4个圆弧，最简单的，圆石到祭坛中心的直线上只有1个石柱，而且此石柱的直径跟此直线重合，这样就要转1个直角弯和2个45度弯。所以我觉得这道题更偏向数学题目，而不是计算机题目
.......[/quote]
没有那么复杂，不要被实数给迷惑了，我们不需要把坐标转换为离散量。球的路径是有规律的，除了转弯都是走的直线，就是从一个柱子的角滚到另一个柱子的角。而且由于障碍物互相遮挡，还可以进一步减少路径。
路径长度 = 直线长度 + 弧线长度。
直线长度等于两个切点之间的距离，也等于两个柱子角之间的距离；（这样就不用计算切点了）。
也许会觉得弧线长度不好计算，但实际上：弧线长度 = （入线与出线的夹角）/ 90度 * 1/4圆周长。
切点最多只需要计算两个，即起点球的切点P与终点球的切点P'
画了个草图，有助于理解
[IMG]http://i133.photobucket.com/albums/q80/yinglong/HUMA.png[/IMG] [quote][b]引用第38楼[i]Gellidus[/i]于[i]2007-04-12 22:42[/i]发表的“”[/b]:
没有那么复杂，不要被实数给迷惑了，我们不需要把坐标转换为离散量。球的路径是有规律的，除了转弯都是走的直线，就是从一个柱子的角滚到另一个柱子的角。而且由于障碍物互相遮挡，还可以进一步减少路径。
路径长度 = 直线长度 + 弧线长度。
.......[/quote]
不错，两个公式都很正确。不过这题目的难点就在于如何选择路线，假如穷举的话，那么每个石柱的每个顶点到其他任何一个顶点都要算作一个路径，并且计算角度（这倒不难，算出个相对与坐标系的角度，到时候两个角度做加减法），当然，由于遮挡关系，有些路径会被剪裁掉，但是如何确定哪些路径被剪裁也是一个问题，或许图形学里的图形剪裁算法可以帮点忙。经过剪裁剩下的路径才能够拿来穷举，不过这样的路径可能还剩下很多，这样很可能会超时
呃，是奥赛，不是ACM……奥赛对程序运行效率有要求么？
页:
[1]
2