Game of Triangles

zobayer RMSTU Bangabandhu Online...
Limits 1s, 512 MB

In order to overcome the boredom during the Covid19 lockdown, you have created a small but clever game, very aptly named, “The Game of Triangles”. The idea is not too complicated. Your program randomly generates a lot of triangles. Each of these triangles is represented in the Cartesian coordinate system with vertices in integer coordinates. But the game hides the triangle from the players. Players take turns and cut the coordinate system (or the 2D plane) with a straight line along either the x-axis or the y-axis. The game continues for as many rounds as you want. In each round, you calculate your score by calculating the number of triangles affected by your cut. A triangle is affected by a cut if both the right side and the left side areas of the cut have positive areas.

However, you quickly realize that this is a very difficult task, especially when your game starts producing a lot of triangles. So now you need to write a program to calculate the number of affected triangles for a given cut.


The first line of the input is the number of test cases TT (T20T \le 20).

Each test case starts with a positive integer NN (2N1052 \le N \le 10^5), the number of generated triangles.

The following 6 integers represent the three coordinates of the triangle (x1,y1)(x1, y1), (x2,y2)(x2, y2), (x3,y3)(x3, y3) in no particular order. It is guaranteed that the triangles will have a positive area, but they can overlap one another arbitrarily.

The following line contains a positive integer MM (2M1052 \le M \le 10^5), the number of cuts. Each of the following M lines contains a cut in the form of ss, vv where s is either ‘x’ or ‘y’ denoting the axis of alignment, and vv is the coordinate value. This represents either the x=vx = v or y=vy = v line equation based on the value of s.

It is guaranteed that 0<=x1,y1,x2,y2,x3,y3,v<1060 <= x1, y1, x2, y2, x3, y3, v < 10^6.


For each test case, first print the test case serial number on a line, followed by MM lines, each containing an integer denoting the number of affected triangles for the corresponding cut in the input. Please check the sample input-output section for formatting details.


1 0 0 2 2 2
1 3 3 5 4 0
5 4 4 5 4 4
x 4
x 1
y 3
y 1
2 7 6 0 0 5
7 1 7 10 11 11
5 10 2 9 6 8
1 9 10 10 4 1
y 6
x 2
x 4
x 9
Case 1:
Case 2:

The input file is very large, please use faster IO.


Login to submit.


88% Solution Ratio
ForkanEarliest, May '21
pathanFastest, 0.2s
Kashbon_BoysLightest, 5.3 MB
steinumShortest, 743B
Toph uses cookies. By continuing you agree to our Cookie Policy.