Seeing the Stars

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.

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

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.

1
3 1 0 0
1 1 1
1 0 1
0 1 1
1 1 3 3 2

Case 1: 2 1.00

Dumbear@WHU

The 6th Central China Invitational Programming Contest and 9th Wuhan University Programming Contest Preliminary