ACM-ICPC-OJ训练营

问题 C: CSGO

时间限制: 36 Sec 内存限制: 128 MB
提交: 4 解决: 1
[提交][状态][讨论版][命题人:]

题目描述

Senior Pan is crazy about CSGO and she is so skilled. She can kill every enemy she spots at the same time, even if they are in different positions.
There are some walls in a map. The locations of enemies are represented by some points and walls are represented by some line segments in the XY plane. The position of senior Pan is also described as a point. Senior Pan can spot an enemy if and only if the segment between them doesn’t intersect with any wall segment. But if there are other enemies on this segment, she can kill all of them.
For some given positions, senior Pan wants to know how many enemies she can kill in these positions. Your Task is to write a program to figure it out.

输入描述

∙ The input contains multiple test cases, each of them are described below.

∙ The first line contains three integers N, M, Q representing respectively the number of enemies, the number of walls and the number of positions senior Pan chooses. For the next N lines, each line contain two integers X and Y, indicating the location of enemies is (X, Y). The next M lines, each line contain four integers X1, Y1, X2, Y2, indicating two endpoints of the wall are (X1, Y1) and (X2, Y2). The last Q lines, each line contain two integers X and Y, indicating the location of senior Pan chooses is (X, Y).

∙ You can assume that walls don’t intersect even if in their endpoints, no enemies have the same location and no enemies are in walls.

∙ N, M <= 10 ^ 4.

∙ Q <= 12.

∙ -10 ^ 6 <= X, Y, X1, Y1, X2, Y2 <= 10 ^ 6

输出描述

For each test case, output "Case #x: " in the first line (without quotes).
For next Q lines, each line output a number which represents the number of enemies senior Pan can kill in her i-th chosen location.

样例输入

3 2 1
1 1
2 2
-1 1
0 1 -1 0
2 -2 2 0
0 0
5 4 2
29 -8
19 33
-46 -44
-38 19
9 -20
40 45 38 18
9 -32 -8 46
33 20 35 -19
22 17 -5 40
19 -38
-17 -21

样例输出

Case #1:
2
Case #2:
3
2