시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 36 | 12 | 9 | 90.000% |
In the JOI plain, people are living with dragons. The JOI plain is a wide coordinate plane with X and Y coordinates. The point with X-coordinate x and Ycoordinate y is denoted by (x, y).
There are N dragons in the JOI plain, numbered from 1 to N. There are M tribes of dragons. The tribes are numbered from 1 to M. The dragon i (1 ≤ i ≤ N) is always staying at the point (Ai, Bi) in the JOI plain, and its tribe is Ci. It is not always the case that dragons of all kinds live in the JOI plain.
In the JOI plain, there are two villages of human beings at the points (D1, E1), (D2, E2). The two villages are connected by a road, which is a line segment connecting the two points of the villages.
The points (A1, B1), . . . , (AN, BN) and the points (D1, E1), (D2, E2) are different from each other. No three of them lie on a straight line.
Sometimes, there are conflicts between tribes of dragons. If the tribe a (1 ≤ a ≤ M) gets hostile to the tribe b (1 ≤ b ≤ M, a ≠ b), every dragon of tribe a launches balls of fire toward all dragons of tribe b. A ball of fire goes straight toward the target. After it gets to the target, it keeps going toward the same direction. Hence the track of a ball of fire is a half-line.
When conflicts between tribes occur, the road must be damaged if a ball of fire from a dragon comes across it. You have a list of Q possible conflicts between tribes of dragons which can occur in the near future. For each possible conflict, you want to calculate the number of balls of fire coming across the road.
Given the information of the dragons and the villages of human beings and a list of possible conflicts between tribes of dragons, write a program which calculates, for each conflict, the number of balls of fire coming across the road.
Read the following data from the standard input.
Write Q lines to the standard output. The j-th line (1 ≤ j ≤ Q) of output contains the number of balls of fire coming across the road in the j-th conflict between tribes.
번호 | 배점 | 제한 |
---|---|---|
1 | 15 | N ≤ 3 000. |
2 | 45 | Q ≤ 100. |
3 | 40 | There are no additional constraints. |
4 2 0 1 1 0 -1 1 1 2 2 -6 1 2 -2 0 2 0 2 1 2 2 1
1 2
In the first conflict between tribes, the following are satisfied:
Hence one ball of fire comes across the road.
In the second conflict between tribes, the following are satisfied:
Hence two balls of fire come across the road.
3 2 -1000000000 -1 1 -999999998 -1 1 0 0 2 999999997 1 999999999 1 1 1 2
1
6 3 2 -1 1 1 0 1 0 3 2 2 4 2 5 4 3 3 9 3 0 0 3 3 6 1 2 1 3 2 1 2 3 3 1 3 2
4 2 4 0 2 1