Lada Malina
Contest: Codeforces Round 433 (Div. 1, based on Olympiad of Metropolises)
Difficulty rating: 3400
Tags: data structures, geometry

After long-term research and lots of experiments leading Megapolian automobile manufacturer «AutoVoz» released a brand new car model named «Lada Malina». One of the most impressive features of «Lada Malina» is its highly efficient environment-friendly engines.

Consider car as a point in Oxy plane. Car is equipped with k engines numbered from 1 to k. Each engine is defined by its velocity vector whose coordinates are (vxi, vyi) measured in distance units per day. An engine may be turned on at any level wi, that is a real number between  - 1 and  + 1 (inclusive) that result in a term of (wi·vxi, wi·vyi) in the final car velocity. Namely, the final car velocity is equal to

(w1·vx1 + w2·vx2 + ... + wk·vxk,   w1·vy1 + w2·vy2 + ... + wk·vyk)

Formally, if car moves with constant values of wi during the whole day then its x-coordinate will change by the first component of an expression above, and its y-coordinate will change by the second component of an expression above. For example, if all wi are equal to zero, the car won't move, and if all wi are equal to zero except w1 = 1, then car will move with the velocity of the first engine.

There are n factories in Megapolia, i-th of them is located in (fxi, fyi). On the i-th factory there are ai cars «Lada Malina» that are ready for operation.

As an attempt to increase sales of a new car, «AutoVoz» is going to hold an international exposition of cars. There are q options of exposition location and time, in the i-th of them exposition will happen in a point with coordinates (pxi, pyi) in ti days.

Of course, at the «AutoVoz» is going to bring as much new cars from factories as possible to the place of exposition. Cars are going to be moved by enabling their engines on some certain levels, such that at the beginning of an exposition car gets exactly to the exposition location.

However, for some of the options it may be impossible to bring cars from some of the factories to the exposition location by the moment of an exposition. Your task is to determine for each of the options of exposition location and time how many cars will be able to get there by the beginning of an exposition.

Input format:
The first line of input contains three integers k, n, q (2 ≤ k ≤ 10, 1 ≤ n ≤ 105, 1 ≤ q ≤ 105), the number of engines of «Lada Malina», number of factories producing «Lada Malina» and number of options of an exposition time and location respectively.

The following k lines contain the descriptions of «Lada Malina» engines. The i-th of them contains two integers vxi, vyi ( - 1000 ≤ vxi, vyi ≤ 1000) defining the velocity vector of the i-th engine. Velocity vector can't be zero, i.e. at least one of vxi and vyi is not equal to zero. It is guaranteed that no two velosity vectors are collinear (parallel).

Next n lines contain the descriptions of factories. The i-th of them contains two integers fxi, fyi, ai ( - 109 ≤ fxi, fyi ≤ 109, 1 ≤ ai ≤ 109) defining the coordinates of the i-th factory location and the number of cars that are located there.

The following q lines contain the descriptions of the car exposition. The i-th of them contains three integers pxi, pyi, ti ( - 109 ≤ pxi, pyi ≤ 109, 1 ≤ ti ≤ 105) defining the coordinates of the exposition location and the number of days till the exposition start in the i-th option.

Output format:
For each possible option of the exposition output the number of cars that will be able to get to the exposition location by the moment of its beginning.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
Images describing sample tests are given below. Exposition options are denoted with crosses, factories are denoted with points. Each factory is labeled with a number of cars that it has.

First sample test explanation:

- Car from the first factory is not able to get to the exposition location in time.
- Car from the second factory can get to the exposition in time if we set w1 = 0, w2 = 1.
- Car from the third factory can get to the exposition in time if we set $$w_{1}=\frac{1}{4}$$, $$w_{2}=\frac{3}{4}$$.
- Car from the fourth factory can get to the exposition in time if we set w1 = 1, w2 = 0.

Example input:
2 4 1
1 1
-1 1
2 3 1
2 -2 1
-2 1 1
-2 -2 1
0 0 2

Example output:
3

Example input:
3 4 3
2 0
-1 1
-1 -2
-3 0 6
1 -2 1
-3 -7 3
3 2 2
-1 -4 1
0 4 2
6 0 1

Example output:
4
9
0

Editorial:
In the original contest there were subtasks for this problem and it's more convinient to understand the editorial going through these subtasks, so we will leave them here.
The key part of a solution is to understand what are the locations that may be accessed from the origin in T seconds. First observation is that we should investigate it only in case when T = 1 because T is simply a scale factor. Let’s denote this set for T = 1 as P.
Group #1. For the first group it’s easy to see that P is a square with vertices in points ( ± 2, 0), (0,  ± 2). So, the first group may be solved with a straightforward O(qn) approach: we iterate through all the factories and check if it's possible to get for cars from i-th factories to the car exposition. We can rotate the plane by 45 degrees (this may be done by the transformation x' = x + y, y' = x - y), after this each query region looks like a square. Therefore, it's necessary to check if point lies inside a square:
Group #2. In the second group propeller velocities are two arbitrary vectors. It can be shown that P will always be a parallelogram centered in the origin, built on vectors 2v1 and 2v2 as sides. Thus, this group is a matter of the same O(qn) approach with a bit more complicated predicate: one should be able to check that an integer point belongs to an integer parallelogram. The key observation is that we may find an appropriate transformation of a plane that transforms this set into a rectangle. Indeed, there always exists an affine transformation performing what we want. As an additional requirement, we want to transform coordinates in such way that they are still integral and not much larger than the original coordinates. The transformation looks like following:
The first expression is a signed distance to the line parallel to the vector v1, and the second one is the signed distance from the line parallel to the vector v2. Easy to see that belonging to some query parallelogram can be formulated in terms of x' and y' independendly belonging to some ranges.
Group #3. Second group should be a hint for the third group. One can find that the set P = {w1v1 + ... + wkvk||wi| ≤ 1} is always a central-symmetric polygon with the center in the origin. Actually, this Polygon is a Minkowski sum of k segments [ - vi, vi]. Minkowski sum of sets A1, A2, ..., Ak is by definition the following set: $$A_{1}+A_{2}+\ldots+A_{k}=\{a_{1}+a_{2}+\ldots+a_{k}\mid a_{1}\in A_{1},a_{2}\in A_{2},\ldots,a_{k}\in A_{k}\}$$. It can be built in $$O(k \log k)$$ time, although in this problem k is very small, so one may use any inefficient approach that comes into his head, like building a convex hull of all points { ± v1 ± v2... ± vk}.
After we found out a form of P, it’s possible to solve the third group of tests in O(qnk) by checking if each possible factory location belongs into a query polygon in O(k) time.
Following groups are exactly the same, but the constraints are higher, they require using some geometric data structure to deal with range queries.
Groups #4 and #5. Fourth group and fifth group are very similar to first and second group correspondingly, but we need to process the requests faster. After the transformation of the plane, the request can be reformulated as "find sum of all factories inside a square", so any 2d data structure may be applied, like a segment tree of segment trees. Another approach is to use a sweeping line algorithm with a segment tree or an appropriate binary search tree, achieving a time complexity $${\mathcal O}((q+n)\log^{2}n)$$ or $${\mathcal O}\left((q+n)\log n\right)$$.
Group #6. To solve the sixth group we need to use a trapezoidal polygon area calculation algorithm applied to our problem. Calculate the sum of points in each of 2k trapezoid areas below each of the sides of a polygon, and then take them with appropriate signs to achieve a result. Such trapezoid area can be seen as a set of points satisfying the inequalities l ≤ x ≤ r and y ≤ kx + b. Under transformation x' = x, y' = y - kx, this area becomes a rectangle, leading us to an $${ \mathcal { O } } ( ( q + n ) k \log n )$$ time solution.