DMOPC '21 Contest 4 P1 - Tree Shopping

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 256M

Problem type

Alice is buying Christmas trees! The shopkeeper, for some reason, keeps the trees arranged in a weird layout. Each of the N trees covers a triangular region in a coordinate plane where one side of the triangle is parallel to the x-axis and another side is parallel to the y-axis. The shop offers Q special Christmas offers, where the i-th offer allows the customer to buy all trees covering the point (x_i, y_i). Alice wonders: for each offer, how many trees is she able to buy?


1 \le N, Q \le 3 \times 10^3

-10^9 \le x_{i1}, y_{i1}, x_{i2}, y_{i2}, x_{i3}, y_{i3}, x_i, y_i \le 10^9

x_{i1} = x_{i2}

x_{i1} \neq x_{i3}

y_{i1} \neq y_{i2}

y_{i1} = y_{i3}

Input Specification

The first line contains 2 integers N and Q.

The next N lines each contain 6 integers x_{i1}, y_{i1}, x_{i2}, y_{i2}, x_{i3}, y_{i3}, describing the coordinates of the vertices of the i-th tree. Specifically, the i-th tree covers the area bounded by the triangle with vertices (x_{i1}, y_{i1}), (x_{i2}, y_{i2}), (x_{i3}, y_{i3}).

The next Q lines each contain 2 integers x_i, y_i, the point included in the i-th offer.

Output Specification

For each offer, output the answer on a new line.

Sample Input

2 5
-2 -3 -2 3 7 -3
-4 1 -4 -6 3 1
2 2
-4 1
1 -2
-2 -1
3 -5

Sample Output



A diagram of the sample case is provided below:


There are no comments at the moment.