CSGO
TimeLimit:10000MS MemoryLimit:65536KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
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.
Input
$\bullet$ The input contains multiple test cases, each of them are described below.
$\bullet$ 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).
$\bullet$ 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.
$\bullet$ N, M <= 10 ^ 4.
$\bullet$ Q <= 12.
$\bullet$ -10 ^ 6 <= X, Y, X1, Y1, X2, Y2 <= 10 ^ 6
$\bullet$ 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).
$\bullet$ 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.
$\bullet$ N, M <= 10 ^ 4.
$\bullet$ Q <= 12.
$\bullet$ -10 ^ 6 <= X, Y, X1, Y1, X2, Y2 <= 10 ^ 6
Output
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.
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.
SampleInput
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
SampleOutput
Case #1: 2 Case #2: 3 2