← 返回题目列表

Codeforces · 144/B

B. 会议

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

超级骗子秘密军事小队的超级骗子秘密会议在超级骗子秘密地点举行。该位置是一个无限平面,引入了笛卡尔坐标系。会议桌被表示为一个矩形,其边与坐标轴平行,其顶点位于平面的整数点处。在属于桌子周边的每个整数点处都有一把椅子,上面坐着一位将军。

飞机上的一些地方装有散热器,以免将军们在冬天被冻住。每个散热器都以数字 ri 为特征——该散热器可以加热的区域的半径。也就是说,如果某个将军与给定散热器之间的距离小于或等于ri,则将军感觉舒适和温暖。这里距离定义为欧氏距离,因此点 (x1, y1) 和 (x2, y2) 之间的距离为 $$\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}$$

每个位于散热器加热区域之外的将军都可能生病。因此,你应该给他带一条温暖的毯子。你的任务是计算你应该带去超级骗子秘密地点的温暖毯子的数量。

已经舒服的将军不需要毯子。此外,即使将军位于多个散热器的加热区域,也不会过热。散热器可以位于平面上的任何整数点,甚至可以位于矩形内部(桌子下方)或周边(直接在某些常规下方)。即使在这种情况下,它们的半径也不会改变。

输入

第一个输入行包含两个相对的表格角 xa、ya、xb、yb 的坐标(xa ≠ xb、ya ≠ yb)。第二行包含整数 n — 散热器的数量 (1 ≤ n ≤ 103)。然后n行包含加热器的坐标“xi yi ri”,数字之间用空格分隔。所有输入数据编号均为整数。所有坐标的绝对值不超过1000,1≤ri≤1000。多个散热器可以位于同一点。

输出

打印唯一的数字——您应该携带的毯子数量。

示例

输入 #1

2 5 4 2
3
3 1 2
5 3 1
1 3 2

输出 #1

4

输入 #2

5 2 6 3
2
6 2 2
6 5 3

输出 #2

0

注意

在第一个示例中,将军坐在以下位置:(2, 2)、(2, 3)、(2, 4)、(2, 5)、(3, 2)、(3, 5)、(4, 2)、(4, 3)、(4, 4)、(4, 5)。其中,4名将军位于加热范围外。他们是以下点的将军:(2, 5)、(3, 5)、(4, 4)、(4, 5)。

在第二个示例中,将军们坐在以下位置:(5, 2)、(5, 3)、(6, 2)、(6, 3)。它们全部位于加热范围内。