print1949. Burek

printBurek

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Baker Crumble has just baked `N` triangular burek pastries (Turkish/Balkanian flaky dough pastry, often filled with cheese or minced meat). Each pastry can be represented in the Cartesian coordinate system as a triangle with vertices in integer coordinate points.
The baker's mischievous son Joey has just taken a large knife and started to cut the pastries. Each cut that Joey makes corresponds to a horizontal (`y\ =\ c`) or vertical (`x\ =\ c`) line in the coordinate system.
Help the baker assess the damage caused by Joey's pastry cutting. Your task is to determine, for each Joey's cut, how many pastries are affected (such that both the left and right parts of the cut pastry have areas greater than zero).
The first line of input contains the positive integer `N` (`2\ ≤\ N\ ≤\ 100\ 000`), the number of burek pastries. Each of the following `N` lines contains six nonnegative integers smaller than `10^6`. These numbers are, in order, the coordinates `(x_1,\ y_1),\ (x_2,\ y_2),\ (x_3,\ y_3)` of the three pastry-triangle vertices. The three vertices will not all be on the same line. The pastries can touch as well as overlap.
The following line contains the positive integer `M` (`2\ ≤\ M\ ≤\ 100\ 000`), the number of cuts.
Each of the following `M` lines contains a single cut line equation: “x = `c`” or “y = `c`” (note the spaces around the equals sign), where `c` is a nonnegative integer smaller than `10^6`.
For each cut, output a line containing the required number of cut pastries.

Sample Input #1

3
1 0 0 2 2 2
1 3 3 5 4 0
5 4 4 5 4 4
4
x = 4
x = 1
y = 3
y = 1

Sample Output #1

0
1
1
2

Sample Input #2

4
2 7 6 0 0 5
7 1 7 10 11 11
5 10 2 9 6 8
1 9 10 10 4 1
4
y = 6
x = 2
x = 4
x = 9

Sample Output #2

3
2
3
2 
Source: COCI 2012/2013, contest #5
loading