编程介的小学生 2017-11-23 15:31 采纳率: 20.5%
浏览 589
已采纳

Seeing the Stars

Problem Description
Dumbear likes to take a walk with his girlfriend, Jing. One day when they were taking a walk, they found that there were so many stars in the sky. But unfortunately, they could see few of the stars because many buildings around blocked their vision.

Jing asked Dumbear how many stars they could see. Jing also wanted to see the most beautiful star of them. Dumbear is very dumb, now he wants you to help him. If you know the locations of all the buildings, the directions of all the stars and the location of Dumbear and Jing, can you calculate the number of stars they could see and the minimum distance they should go for seeing the most beautiful star?

You can assume all the buildings are cuboids lay on the ground; all the stars are strictly above the ground and are infinite far away. You can also assume all the buildings do not intersect or touch one another and the location of Dumbear and Jing is strictly outside any building. Note that we consider a building blocks their vision if and only if the vision goes through the building strictly. Also note that no one can go through any building.

Input
The first line contains a single integer T, indicating the number of test cases.
Each test case begins with four integers N, M, X, Y indicate the number of the stars, the number of the buildings, and the coordinates of Dumbear and Jing on the ground.
Then N lines follow, each line contains three integers Xi, Yi, Zi indicate a star’s direction. If your location is (x, y) on the ground, then the star will be in the direction (x, y, 0) => (x + Xi, y + Yi, Zi). Note that the most beautiful star is always the first.
Then M lines follow, each line contains five integers X1i, Y1i, X2i, Y2i, Hi indicate the building’s lower left coordinates, upper right coordinates on the ground and the height of it.

Technical Specification

  1. 1 <= T <= 10020
  2. 1 <= N <= 1000 Note for more than 99% of the test cases, 1 <= N <= 10
  3. 1 <= M <= 20 Note for more than 99% of the test cases, 1 <= M <= 5
  4. 0 <= |X|, |Y|, |Xi|, |Yi|, |X1i|, |Y1i|, |X2i|, |Y2i| <= 1000
  5. X1i < X2i, Y1i < Y2i, 10 <= Zi, Hi <= 100

Output
For each test case, output the case number first, then the number of the stars they can see directly and the minimum distance they should go to see the most beautiful star. You should round the distance to 2 digits after the decimal point.

Sample Input
1
3 1 0 0
1 1 1
1 0 1
0 1 1
1 1 3 3 2

Sample Output
Case 1: 2 1.00

  • 写回答

1条回答 默认 最新

  • threenewbee 2018-06-11 16:18
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀