编程介的小学生 2017-01-14 07:22 采纳率: 20.5%
浏览 938
已采纳

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条回答 默认 最新

  • threenewbee 2017-01-21 16:44
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)