#2214. Dragon 2

    ID: 2214 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1718来源:qoj.ac数据:公开样例线段树并查集

Dragon 2

Dragon 2

题目描述

The 16th Japanese Olympiad in Informatics (JOI 2016/2017) Spring Training Camp/Qualifying Trial March 19–25, 2017 (Komaba/Yoyogi, Tokyo) Contest Day 4 – Dragon 2 Dragon 2 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 Y- coordinate 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. Task 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. Input Read the following data from the standard input. • The first line of input contains two space separated integers N, M. This means there are N dragons in the JOI plain, and there are M tribes of dragons. • The i-th line (1 ≤i ≤N) of the following N lines contains three space separated integers Ai, Bi,Ci. This means the dragon i (1 ≤i ≤N) is staying at the point (Ai, Bi) in the JOI plain, and its tribe is Ci. • The following line contains four space separated integers D1, E1, D2, E2. This means there are two villages of human beings at the points (D1, E1), (D2, E2) in the JOI plain. Dragon 2– 1 / 4 The 16th Japanese Olympiad in Informatics (JOI 2016/2017) Spring Training Camp/Qualifying Trial March 19–25, 2017 (Komaba/Yoyogi, Tokyo) Contest Day 4 – Dragon 2 • The following line contains an integer Q, the number of possible conflicts between tribes of dragons. • The j-th line (1 ≤j ≤Q) of the following Q lines contains two space separated integers F j,G j. This means, in the j-th possible conflict, the tribe F j gets hostile to the tribe G j. Output 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. Constraints All input data satisfy the following conditions. • 2 ≤N ≤30 000. • 2 ≤M ≤N. • −1 000 000 000 ≤Ai ≤1 000 000 000 (1 ≤i ≤N). • −1 000 000 000 ≤Bi ≤1 000 000 000 (1 ≤i ≤N). • 1 ≤Ci ≤M (1 ≤i ≤N). • −1 000 000 000 ≤D1 ≤1 000 000 000. • −1 000 000 000 ≤E1 ≤1 000 000 000. • −1 000 000 000 ≤D2 ≤1 000 000 000. • −1 000 000 000 ≤E2 ≤1 000 000 000. • The N + 2 points (A1, B1), . . . , (AN, BN), (D1, E1), (D2, E2) are different from each other. No three of them lie on a straight line. • 1 ≤Q ≤100 000. • 1 ≤F j ≤M (1 ≤j ≤Q). • 1 ≤G j ≤M (1 ≤j ≤Q). • F j , G j (1 ≤j ≤Q). • (F j,G j) , (Fk,Gk) (1 ≤j < k ≤Q). Dragon 2– 2 / 4 The 16th Japanese Olympiad in Informatics (JOI 2016/2017) Spring Training Camp/Qualifying Trial March 19–25, 2017 (Komaba/Yoyogi, Tokyo) Contest Day 4 – Dragon 2 Subtask There are 3 subtasks. The score and additional constraints of each subtask are as follows: Subtask 1 [15 points] • N ≤3 000. Subtask 2 [45 points] • Q ≤100. Subtask 3 [40 points] There are no additional constraints. Sample Input and Output Sample Input 1 Sample Output 1 4 2 1 0 1 1 2 0 -1 1 1 2 2 -6 1 2 -2 0 2 0 2 1 2 2 1 In the first conflict between tribes, the following are satisfied: • The ball of fire launched by the dragon 1 toward the dragon 3 does not come across the road. • The ball of fire launched by the dragon 1 toward the dragon 4 does not come across the road. • The ball of fire launched by the dragon 2 toward the dragon 3 comes across the road. • The ball of fire launched by the dragon 2 toward the dragon 4 does not come across the road. Hence one ball of fire comes across the road. In the second conflict between tribes, the following are satisfied: • The ball of fire launched by the dragon 3 toward the dragon 1 comes across the road. • The ball of fire launched by the dragon 3 toward the dragon 2 comes across the road. Dragon 2– 3 / 4 The 16th Japanese Olympiad in Informatics (JOI 2016/2017) Spring Training Camp/Qualifying Trial March 19–25, 2017 (Komaba/Yoyogi, Tokyo) Contest Day 4 – Dragon 2 • The ball of fire launched by the dragon 4 toward the dragon 1 does not come across the road. • The ball of fire launched by the dragon 4 toward the dragon 2 does not come across the road. Hence two balls of fire come across the road. Sample Input 2 Sample Output 2 3 2 1 -1000000000 -1 1 -999999998 -1 1 0 0 2 999999997 1 999999999 1 1 1 2 Sample Input 3 Sample Output 3 6 3 4 2 -1 1 2 1 0 1 4 0 3 2 0 2 4 2 2 5 4 3 1 3 9 3 0 0 3 3 6 1 2 1 3 2 1 2 3 3 1 3 2 Dragon 2– 4 / 4

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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

样例 2

3 2
-1000000000 -1 1
-999999998 -1 1
0 0 2
999999997 1 999999999 1
1
1 2
1