16577번 - Artilleries and Defensive Walls 다국어

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 (xk, yk) where yk < 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. Your task in this problem is to determine the number of Norland’s artilleries which can be observed from each proposed watchtower position.

Input begins with a line containing three integers: N M Q (1 ≤ N ≤ 40000; 0 ≤ M ≤ 5; 1 ≤ Q ≤ 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⁶ ≤ x_i ≤ 10⁶; 0 < y_i ≤ 10⁶) representing the position of the ith artillery for i = 1 . . . N. The next M lines, each contains three integers: x_j1 x_j2 y_j (−10⁶ ≤ x_j1 < x_j2 ≤ 10⁶; 0 < y_j ≤ 10⁶) representing the position of the jth defensive wall for j = 1 . . . M. The next Q lines, each contains two integers: x_k y_k (−10⁶ ≤ x_k ≤ 10⁶; −10⁶ ≤ y_k < 0) representing a proposed position for the watchtower.

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.