← 返回题目列表

Codeforces · 853/E

E. 拉达·马利纳

中文机器翻译题面 查看原题

经过长期研究和大量实验,领先的Megapolian汽车制造商“AutoVoz”发布了一款名为“Lada Malina”的全新车型。 “Lada Malina”最令人印象深刻的特点之一是其高效环保的发动机。

将汽车视为 Oxy 平面上的一个点。汽车配备了 k 个发动机,编号从 1 到 k。每个引擎由其速度矢量定义,其坐标为(vxi,vyi),以每天的距离单位测量。发动机可以在任何级别 wi 上启动,wi 是 - 1 和 + 1(含)之间的实数,导致最终汽车速度中的项为 (wi·vxi, wi·vyi)。即,最终汽车速度等于

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

正式来说,如果汽车在一天中以恒定的 wi 值移动,那么它的 x 坐标将根据上面表达式的第一个分量而变化,并且它的 y 坐标将根据上面表达式的第二个分量而变化。例如,如果所有 wi 都等于 0,则汽车不会移动,如果除 w1 = 1 之外所有 wi 都等于 0,则汽车将以第一个发动机的速度移动。

Megapolia 有 n 个工厂,其中 i 个位于 (fxi, fyi)。在第 i 个工厂里,有人工智能汽车“Lada Malina”已准备好运行。

为了增加新车的销量,“AutoVoz”将举办国际汽车博览会。展览地点和时间有 q 个选项,其中第 i 个展览将在 ti 天内在坐标为 (pxi, pyi) 的点发生。

当然,在《AutoVoz》上,我们将把尽可能多的新车从工厂带到展会现场。汽车将通过在一定水平上启用发动机来移动,以便在博览会开始时汽车准确地到达博览会地点。

然而,对于某些选项,可能无法在博览会期间将汽车从某些工厂运至博览会地点。您的任务是确定博览会地点和时间的每个选项,在博览会开始时有多少辆汽车能够到达那里。

输入

输入的第一行包含三个整数 k、n、q(2 ≤ k ≤ 10、1 ≤ n ≤ 105、1 ≤ q ≤ 105),分别为《Lada Malina》的发动机数量、生产《Lada Malina》的工厂数量以及展会时间和地点的选项数量。

以下 k 行包含 «Lada Malina» 发动机的描述。其中第 i 个包含两个整数 vxi、vyi (- 1000 ≤ vxi, vyi ≤ 1000),定义第 i 个发动机的速度矢量。速度矢量不能为零,即vxi和vyi至少有一个不等于0。保证没有两个速度矢量共线(平行)。

接下来的 n 行包含工厂的描述。其中第 i 个包含两个整数 fxi、fyi、ai (- 109 ≤ fxi, fyi ≤ 109, 1 ≤ ai ≤ 109),定义第 i 个工厂位置的坐标以及位于该工厂的汽车数量。

以下 q 行包含汽车博览会的描述。其中第 i 个包含三个整数 pxi、pyi、ti(- 109 ≤ pxi、pyi ≤ 109、1 ≤ ti ≤ 105),定义第 i 个选项中展览地点的坐标以及距离展览开始的天数。

输出

对于博览会的每个可能选项,输出在博览会开始时能够到达博览会地点的汽车数量。

示例

输入 #1

2 4 1
1 1
-1 1
2 3 1
2 -2 1
-2 1 1
-2 -2 1
0 0 2

输出 #1

3

输入 #2

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

输出 #2

4
9
0

注意

下面给出了描述样本测试的图像。博览会选项用叉表示,工厂用点表示。每个工厂都标有其拥有的汽车数量。

第一个样本测试说明:

- 第一工厂的车辆无法及时到达展会地点。
- 如果我们设置w1 = 0,w2 = 1,二厂的汽车就能及时到达博览会。
- 如果我们设置$$w_{1}=\frac{1}{4}$$、$$w_{2}=\frac{3}{4}$$,那么三厂的汽车就能及时到达展会。
- 如果我们设置w1 = 1,w2 = 0,四厂的汽车就能及时到达博览会。