2 shunfurh shunfurh 于 2017.01.14 15:22 提问

POJ3591 :Ants and Aphides

描述
There is a big villa far away from the city, and no one lived there for a long time. In the room on the first floor, ants have already built their community under a fixed cuboid solid in the corner of this room, which is illustrated in Figure 1.

Figure 1
There is a hole at Point A which is the entrance and exit of the ants' nest and the ants will start their aphis explorer here. Aphides grow on the vertical surfaces of the cuboid solid. Everyday the ants go out to one of the aphides and take it back. The ants can go to the aphis directly if they know where it grows though they may not see it.
It's dangerous somewhere in the villa! For the perennial acid rain in this area, and also no one came to maintain this villa for years, all the floors of the villa have big holes.
As you see in Figure 1, the acid rain has destroyed somewhere on the roof of the solid. Just image, the destroyed area is the only area on the cuboid roof surface where you can see the sky when you looking up. Thus, when the ants are out to fetch aphides they will keep away from the acid-destroyed area.
For simplicity, we assume that:
The aphides do not move.
Each floor has only one hole.
All the holes on the floors are regular convex polygons.
The acid rain falls strictly vertically in the villa.
The brim of the acid-destroyed area is safe for the ants.
The aphis ants will not dig holes for fetching aphides.
Now give the coordinate of ONE aphis and help the ants to calculate the shortest path to get to it.
输入
The first line of the input is an integer T which indicates the number of test cases.
Each of the case, the first line will be the three integers L, W, and H, (0 < L, W, H ≤ 10000 indicate the length (x-coordinate), width (y-coordinate) and the height (z-coordinate) of the solid.
The next line follows an integer K (0 ≤ K ≤ 10), indicating the number of floors with holes above the solid (including the roof of the villa). Then follows K lines describe the holes. Each of the K lines begin with an integer indicating the number Ni (3 ≤ Ni ≤ 100) of points of the convex polygons of the hole, the next Ni pairs of integers will be the continuous points of the hole counter-clockwise, you can assume that all the coordinates of the points are in the range (0, 10000). The floors are all horizontal and you need not to know exactly how high they are.
Then follows a three-dimensional integer coordinate (x, y, z) indicating the location of the target aphis. You can assume that this point is always on the plane X = L or Y = W.
The original point of the coordinate system is inside the solid, and the coordinate of Point A is (0, 0, H).
输出
Output a real number with a precision of three decimals of the shortest path for each test case.
 
样例输入
1
10 10 10
2
4 2 1 8 1 8 8 2 8
4 2 2 8 2 8 9 2 9
10 10 0
样例输出
22.668

1个回答

caozhy
caozhy   Ds   Rxr 2017.01.22 00:44
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
.NET开发辅助工具(三)---ANTS Memory Profiler
在使用.NET进行程序开发的时,可能会碰到内存溢出、或者程序运行时内存占用过大。特别是医院的PACS、RIS系统对于图片的操作比较频繁,对于程序内存的控制特别的重要,这时候可以使用.NET的内存分析工具ANTS Memory Profiler进行程序的内存分析。 介绍         工具下载地址:http://www.red-gate.com/products/  文档地址:http
ANTS Memory Profiler 8 安装包+激活工具+教程
内存优化分析工具,使用离线激活模式,亲测可用,永久有效!
ANTS Performance Profiler 破解使用
http://blog.csdn.net/wangjia184/article/details/7746089
.NET 内存监测(Ants Memory Profiler)
背景给客户开发了一个WPF应用,每隔一段时间就会很卡,推测是内存泄漏引起。需要监测内存使用情况。使用的工具Ants Memory Profiler 百度网盘下载地址使用教程入门使用 参考文档
ANTS Memory Profiler - .NET内存泄漏分析工具
ANTS Memory Profiler是RedGate的一款专门用于.NET程序内存分析的工具: http://www.red-gate.com/products/ants_memory_profiler/ Check the memory usage of your .NET program Find memory leaks within minutes Opti
RedGate ANTS Profiler 4.3 破解
破解声明:我的破解仅用于研究,请勿用于商业用途,需要使用请购买正版软件。 最新RedGate ANTS Profiler 4.3破解,安装说明: 1)下载ANTS Profiler 4.3,地址:http://www.red-gate.com/products/ants_profiler/index.htm 2)安装试用版程序 3)使用破解文件覆盖试用版程序安装目录中的对应文件。 注:这个破解修正了ANTS Memory Profiler 4的版本号,原有程序的版本号是4.3.0.126,但是实际版本是4.3.0.198, 所以原版程序会提示升级,实际上并没有升级程序 这个破解去掉了全部程序集的强命名,所以不需要绕过对license组件的强命名验证。 需要RedGate其他破解的请看这里:http://blog.csdn.net/Danny_Su/archive/2008/09/29/2994139.aspx Danny Su 2009-2-26
ANTS Memory Profiler
http://www.simple-talk.com/dotnet/.net-tools/profiling-the-memory-usage-of-a-.net-application-with-ants-memory-profiler-5/ Introduction Automatic memory management in .NET makes developm
ANTS Performance Profiler 8 安装包+激活工具+教程
性能调优的好东西,采用离线激活的模式,亲测可用,永久有效,内附激活教程
POJ 1852 Ants(弹性碰撞问题)
Ants Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 12607 Accepted: 5525 Description An army of ants walk on a horizontal pole of
ants performance profiler 8 安装文件+破解文件+破解手册
ants performance profiler 8 性能测试工具 超级好用 .net 性能瓶颈查找