Artilleries and Defensive Walls (Problem E, 2018 ICPC Asia Jakarta Regional Contest, 2018)
Time limit: 1 sec
Memory limit: 256MB
Author: Vincentius Madya Putra I.

# Problem Statement

Sauville has been engulfed in a devastating war with its neighboring country, Norland, for centuries. Their border can be represented as a straight horizontal line $y = 0$, where all areas for $y < 0$ belong to Sauville and all areas for $y > 0$ belong to Norland.

Norland has deployed $N$ of its artilleries at position $(x_i, y_i)$ where $y_i > 0$. In addition, Norland also has built $M$ defensive walls. Each defensive wall can be represented as a tuple $(x_{j1}, x_{j2}, y_j)$, which is a horizontal line segment spanned from $(x_{j1}, y_j)$ to $(x_{j2}, y_j)$, where $x_{j1} < x_{j2}$ and $y_j > 0$. It is known to Sauville that no Norland’s artillery is located at any of its defensive walls (including its endpoints), and no two artilleries are at the same position. It is also known that no two walls (including their endpoints) are sharing a common point.

Sauville has decided to build a watchtower to observe any suspicious activity on any Norland’s artilleries. As the cost to build one watchtower is almost astronomical for Sauville, they can only afford to build one. Thus, $Q$ position candidates $(x_k, y_k)$ where $y_k < 0$ for the watchtower have been proposed. If the watchtower is built at $(x, y)$, then all artilleries which lie on the _line-of-sight_ from $(x, y)$ can be observed (visible) by the watchtower. A position $(x_i, y_i)$ lies on the line-of-sight from $(x, y)$ if and only if the straight line connecting $(x_i, y_i)$ and $(x, y)$ does not intersect with any defensive walls (including its endpoints); in other words, there should be no point $(x', y')$ such that $(x', y')$ lies on a defensive wall and also on the line segment between $(x_i, y_i)$ and $(x, y)$. Note that an artillery does not affect the visibility of any other artilleries from the watchtower point.

Your task in this problem is to determine the number of Norland’s artilleries which can be observed from each proposed watchtower position.

# Input

Input begins with a line containing three integers: $N$ $M$ $Q$ $(1 \leq N \leq 40000;\ 0 \leq M \leq 5;\ 1 \leq Q \leq 40000)$ representing the number of artilleries, the number of defensive walls, and the number of proposed watchtower positions, respectively. The next $N$ lines, each contains two integers: $x_i$ $y_i$ $(-10^6 \leq x_i \leq 10^6;\ 0 < y_i \leq 10^6)$ representing the position of the $i^{th}$ artillery for $i = 1 \dots N$. The next $M$ lines, each contains three integers: $x_{j1}$ $x_{j2}$ $y_j$ $(-10^6 \leq x_{j1} < x_{j2} \leq 10^6;\ 0 < y_j \leq 10^6)$ representing the position of the $j^{th}$ defensive wall for $j = 1 \dots M$. The next $Q$ lines, each contains two integers: $x_k$ $y_k$ $(-10^6 \leq x_k \leq 10^6;\ -10^6 \leq y_k < 0)$ representing a proposed position for the watchtower.

# Output

For each proposed watchtower position in the same order as input, output in a line a single integer representing the number of Norland’s artilleries which can be observed from the proposed position.

# Sample Input
```
6 2 3
0 2
0 15
5 7
15 15
35 12
45 10
5 20 5
25 40 10
0 -5
5 -10
20 -15
```
# Sample Output
```
4
3
2
```
# Explanation for the sample input/output

The position of all artilleries, defensive walls, and proposed watchtowers are shown in the following figure.

![IMAGE](icpc-jakarta-2018-war-1.png)

20
(0,15)          (15,15)
(35,12)
(45,10)
10                 (5,7)

(0,2)
Norland
0
Sauville

(0,-5)
-10
(5,-10)

(20,-15)

-10         0          10         20         30         40         50

- The first proposed watchtower (0, −5) can observe 4 artilleries, i.e. at (0, 2), (0, 15), (5, 7), and (45, 10).
- The second proposed watchtower (5, −10) can observe 3 artilleries, i.e. at (0, 2), (0, 15), and (45, 10).
- The third proposed watchtower (20, −15) can observe 2 artilleries, i.e. at (0, 2) and (45, 10).

Sample inputs:
6 2 3
0 2
0 15
5 7
15 15
35 12
45 10
5 20 5
25 40 10
0 -5
5 -10
20 -15

Sample outputs:
4
3
2

# Solution Analysis

A naïve solution to answer each query $q$ would be simply iterating through each artillery point $p \in P$ and check whether the line connecting $q$ and $p$ intersect with any wall. This solution has a complexity of $O(NM)$ per query, and for this problem, this solution will get you **TIMELIMIT** as the number of artilleries and queries may reach $40000$ each. We need to do better.

First, let’s consider the case when $M = 1$ ($M = 0$ is trivial and not interesting). We can answer each query in $O(\log N)$ time with a preprocess step (for all queries) of $O(N \log N)$. For each point $p$ which lies above the wall, project the wall from point of view $p$ to $y = 0$. Let the projection be $p_L$ and $p_R$. Let $S$ be the collection of all $\langle p_L, p_R \rangle$. Now, to answer a query $q$, do a similar thing, i.e. project the wall from $q$’s point of view to $y = 0$. Let the projection be $q_L$ and $q_R$. The number of artilleries which cannot be seen from $q$ will be equal to the number of tuples $\langle p_L, p_R \rangle$ in $S$ such that $p_L \leq q_L \leq q_R \leq p_R$. You can use any 2-dimensional data structure to answer such query; however, as the data are static (no alteration), a much simpler solution like binary search is better (you also want to avoid a large constant factor in your solution).

![IMAGE](icpc-jakarta-2018-war-2.png)

Now, to handle $M > 2$, we can use the **inclusion-exclusion principle**. Let $\langle p_L^m, p_R^m \rangle$ be the intersection projection of set of wall $m$ from $p$’s point of view to $y = 0$. In other words, any line from any position $(x, 0)$ where $x = [p_L^m, p_R^m]$ to $p$ will intersect with all $m$. Calculate for all possible set of wall $m$, and the answer to each query then can be computed simply by the inclusion-exclusion principle. The preparation step (one-time) for this approach is $O(2^M N (M + \log(NM)))$, and the query processing is $O(2^M (M + \log(NM)))$ per query.

Special judge (C++ scorer):