It is now year 2020, people dont install games in their hard disk now as they only play online games. “Battle of the triangle” has evolved as the most popular online game now. The game is played between two armies: One army is controlled by 100 players from one city and another army is controlled by another 100 player from another city. At the start of the game there is a toss. The winner of the toss is marked Team A and the loser is marked team B. The battle field is already generated for the two teams. Battle field means a two dimensional plane where positions of the soldiers are given by two dimensional Cartesian Coordinate System and position of the tanks are also given by two dimensional Cartesian Coordinate System. There are three boundary lines which create a triangle and everything inside the triangle belongs to Team A and everything in the reciprocal regions of the triangle belongs to team B, as shown in the picture below. The other three regions are neutral regions. Team A can move the boundary lines to select his own triangle. But of course he cannot rotate the boundary lines. There is a central server where the players have to connect to play this game and it is al- ready mentioned that each team consists of 100 players. Each team has a Captain. The captain of Team A initially selects the three boundary lines. When the boundary lines are selected the server has to give the Captain of Team A two information: The difference between sol- dier number of Team A and Team B and the difference between the tank number of Team A and Team B so that the captain can rethink his strategy. But as many teams all around the world play at the same time using the same battle field so the server has to answer many queries simultaneously. Your job is to write a program that does this job very efficiently. Input The input file contains several sets of inputs. The description of each set is given below: Figure: Dark Gray is the region of A, Light Gray is the region of B and white is the neutral region. Each set starts with three integers S, T and Q. Here S (0 < S ≤ 50000) is the total number of soldiersinthemap,T (0<T ≤50000)isthetotalnumberofTanksinthemapandQ(0<Q≤10000) is the total number of queries the server has to handle. Each of the next S lines contain two integers xi,yi (|xi|,|yi| ≤ 10000000) which denotes the Cartesian coordinates of the soldiers. Each of the next T lines contains two integers xj,yj (|xj|,|yj| ≤ 10000000) which denotes the coordinates of the tanks. These lines are followed by 3Q lines as each query consists of three lines of inputs. First line contains three integers A1, B1, C1, second line contains three integers A2, B2, C2 and third line contains three integers A3,B3,C3. These denotes that captain of team A has placed the first boundary line along the straight line A1x + B1y + C1 = 0 the second boundary line along the straight line along the straight line A2x + B2y + C2 = 0 and the third boundary line along the straight line A3x + B3y + C3 = 0. So the region for team A is the triangle formed by these three straight lines and the region for team B is three reciprocal regions of this triangle. For each query you have to find the soldier number difference
2/3 between team A and B and tank number difference between team A and team B. The figure below corresponds to the sample input. You can of course assume that in a set of input the first line of each query are parallel to one another, and this is true for second lines of each query and third line of each query as well. You can also assume that (|A1|, |B1|, |A2|, |B2| ≤ 1000), (|C1|, |C2| ≤ 10000000), no two lines in a query are parallel each other, the three lines in a query are not concurrent and no soldier and no tank will be on any of the three boundary lines. Input is terminated by a case where S = T = Q = 0. This case should not be processed. The input file size is around 6 MB. This will give you some idea on how efficient your program needs to be. Output For each set of input produce (Q+1) lines of outputs. First line contains the battle field serial. Each of the next Q lines contains output for one query. For each query output in a single line the serial of the query followed by two integers DS and DT separated by a single space. Here DS is the difference of number of soldiers between team A and team B, and DT is the difference of number of tanks between team A and team B. Look at output for sample input for details. Although this problem does not have multiple answers, due to unstable behavior of floating-point number is linux a difference of one between judge solution and contestant solution will be accepted. So there is a special judge for this problem. Sample Input 852 -1 8 -7 3 -2 1 -2 -1 -5 -2 6 -1 2 -4 -4 -5 17 11 34 -6 5 -12 -6 2 -2 10 The figure above corresponds to the sample input.
3/3 -2 6 6 -5 -3 1 1 -1 5 1 -3 -3 5 3 -15 000 Sample Output Battle Field 1: Query 1: 1 -1 Query 2: 1 -1