OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SDOI2005】屠龙传说-屠龙枪卷

【题目描述】

先知看到修玛取回的药草,满意地点了点头。他对修玛说:“跟我来”。修玛顺从地跟着先知走到了他的房间里。先知的房间很大,四周满是书架,整整齐齐地摆放着一排排书籍。房间中间的圆桌上摆放着一个巨大的水晶球,它发出的荧光照亮了整个房间。先知走到一排书架前,从中抽出一本薄薄的书来。这本书看起来十分古老,纸张都变成了黄色,有的地方已经发黑。修玛想,这本书的历史大概有好几百年了吧。先知示意修玛坐下,他翻开手中的书,对修玛说道:“我已经研究这本书很久了。它是用一种古老的文字写成的,记载了一个十分古老的传说。书中提到,普通的武器是无法伤害巨龙的,只有诸神合力锻造的屠龙枪才能消灭它。为了防止屠龙枪被滥用,神把它封印在卡基思山上,只有拥有超人的勇气、力量和智慧的人才能解开这个封印。千百年来,很多人都想得到屠龙枪的力量,然而从没有人成功过。我查阅了所有有关屠龙枪的记载,悉心地研究那些资料,得知屠龙枪被封印在山顶的神殿中,而要解开这道封印,就必须把神殿中的一块巨大的圆石推到神殿祭坛的中心,然后念出解开封印的咒语。”修玛问道:“那句咒语应该已经失传了吧?”“不,恰恰相反。”先知说,“这句咒语一直记载在这本书中,并被完好地保存下来。”“那么,剩下的只是把圆石推到祭坛的中心了。”修玛自信地笑了。然而先知却摇了摇头,“不,修玛,事情没有你想象的那么简单。爬上卡基思山就不是一件容易的事。它高耸入云,四周都是光秃秃的石壁,几乎没有落脚的地方。只有真正的勇士才能爬得上去。那块圆石也不是那么容易就能推动的,非得有超常的力量不可。这些东西,修玛你都有。但如果仅仅只有这些,那么屠龙枪早已被人拿到手了。书中不是说了么,要有勇气、力量和智慧。智慧才是真正的关键。如果在固定时间内不能把那块圆石推到祭坛的中心,那么圆石便会自动滚回原处,同时推石的人将永远无法再次推动这块圆石。而且不管你用多大力气推,这块圆石都不可能滚动得像你希望的那样快,我估计只有按照最短路线去推这块圆石,才能在固定时间内把它推到祭坛中心。神殿中又有着大大小小的石柱,有些石柱与石柱之间的空隙很小,根本就推不过去。正因为这种种困难,才没有人能够从神殿中取走屠龙枪。”修玛沉默了一会儿,说:“不管如何,我也要去试一试。如果我不能拿到屠龙枪,就没有人能够拿到它了。”先知点了点头,说:“去吧,修玛。记住,用你的智慧。”

修玛骑马奔驰了十天十夜,终于来到了卡基思山脚下。正如先知所说的那样,这座山根本就没有路可以上去,甚至找不到可以落脚的地方。然而修玛凭着他的勇气以及熟练的技巧,爬上了山顶。他走进神殿,一眼就看到了那块巨大的圆石。修玛该怎么做,才能把圆石推到祭坛的中心呢?

你的任务是计算出把圆石推到祭坛中心的最短路线长度。所谓推到祭坛中心是指圆石的中心与祭坛中心重合。圆石中心的初始位置以及祭坛中心的位置是已知的。圆石半径为R,它可以朝着任意方向滚动。洞中所有石柱均为正四棱柱,大小不一。在推动圆石的过程中,要求圆石中心与所有石柱的距离均不小于R,否则圆石将被石柱阻挡而不能继续滚动。

【输入】

输入文件第一行包含了五个实数,依次表示圆石中心的初始位置的x坐标、y坐标、圆石半径R、祭坛中心的位置的x坐标以及y坐标。第二行包含一个整数N(0<=N<=20),表示神殿中石柱的数目。接下去N行每行包含三个实数,给出了一根石柱的信息。第I+2行的三个实数依次表示第I根石柱左下角x坐标、y坐标以及该石柱的边长。所有实数均精确到2位小数,范围在0到1000之内。

【输出】

输出文件仅包含一个实数表示把圆石推到祭坛中心的最短路线长度,输出结果保留到两位小数。你可以假设总存在一条把圆石推到祭坛中心的路。

【输入样例】

0 0 10 30 40

1

10 10 10

【输出样例】

57.93

【数据范围】

0<=N<=20

【题解】

这题不是很难,但写起来很令人掀桌(╯‵□′)╯︵┻━┻

首先我们把要推的圆石缩成它的中心点,把石柱的四边都向外平移R,再把四个顶点都变成半径为R的圆,现在的问题就等价于圆石中心点到祭坛中心的最短路。我们求出两个中心和所有圆的切线、圆和圆之间的公切线,把所有切点称为关键点。接下来给关键点连边,如果两个关键点之间没有阻挡就连上一条权值为两点之间距离的边,如果两个关键点在同一个石柱上,就连上一条权值为两点绕着石柱走最近距离的边。最后随便拿个算法求圆石中心点到祭坛中心最短路就是答案了。

具体的实现就不多说了,计算几何基础的东西基本上都用上了,随便搞搞掀掀桌,就调出来了……

【代码】

这份代码有漏洞,时间和精度上太卡,或许有减少关键点的办法?

http://paste.ubuntu.com/10686689/

评论

© OI技术宅 | Powered by LOFTER