P4623 [COCI 2012/2013 #6] BUREK

COCI

Given $N$ triangles and $M$ lines. Each line is either parallel to the $x$ axis or parallel to the $y$ axis. For each of the $M$ lines, find how many triangles it passes through. **(A line passes through a triangle if and only if the line can split the triangle into two polygons whose areas are both greater than zero.)**

The first line contains a positive integer $N$, the number of triangles. The next $N$ lines each contain three coordinates $(x_1,y_1)$, $(x_2,y_2)$, $(x_3,y_3)$, representing three points. These three points are not collinear and form a triangle. All coordinates are non-negative integers, and triangles may overlap. The next line contains a positive integer $M$, the number of lines. The next $M$ lines each contain a string `x = c` or `y = c` (note the spaces on both sides of the equals sign), describing a line. Here `c` is a non-negative integer.

For each line, output one integer, the number of triangles it passes through.

**Constraints** For $40\%$ of the testdata, $M \le 300$. For another $40\%$ of the testdata, all triangle coordinates are $< 1000$. For $100\%$ of the testdata, $2 \le N,M \le 10^5$, and $0 \le x_1,y_1,x_2,y_2,x_3,y_3 < 10^6$. Translated by ChatGPT 5