問題文
高桥君管理着世界上最大的花园之一。这个花园里有世界上最美丽的花朵。 1 只有年轮在绽放。 这个花园里的点用它们与世界上最大的花的距离来表示。从花东边 x ,向南 y 移动点的位置 表示为 (x, y) 。 高桥君很有条理, 使得 x 和 y 都是整数的点 (x, y) 必须是 1 我正在种植一圈花。我没有在其他地方种植它。
更正式地说,在笛卡尔坐标上的所有网格点上, 1 种植了一圈花,原点种植了世界上最大的花。除网格点外,不种植任何花卉。
世界上最大的花需要大量的水。这就是高桥君在花园里的原因。 N 我们决定在此位置安装洒水器。 任何洒水装置 x 也是 使得 y 也是整数的点 它将安装在 (x, y) 。在同一个位置 将安装不超过 2 个喷头。 每个喷头以圆形图案喷洒水。如果增大半径,可以浇灌更大的面积,但会浪费金钱,所以 每个洒水器喷洒的水量勉强够到世界上最大的花朵。换句话说,喷头喷出的水的半径与世界上最大的花和喷头之间的距离相匹配。
当高桥打开洒水器时,他很好奇会给多少朵花供水。
给定每个喷头的位置,找出要浇水的花朵数量。
入力
输入将以以下格式从标准输入给出。
N x_1 y_1 x_2 y_2 : x_N y_N
- 1 行表示要安装的喷头数量。 N(1≦N≦10^5) 给出。
- 继续 N 行数过多 i 行中, 2 整数 x_i, y_i(-10^5≦ x_i, y_i ≦ 10^5) 用空格分隔。这是 第i个喷头的位置是(x_i, y_i)。
- i \neq j 如果 (x_i,y_i) \neq (x_j,y_j)成立
- 总是 如果满足 (x_i,y_i) \neq (0, 0)成立
部分点
针对此问题设置了部分分数。 如果正确答案是满足
- N≦100 和 -100 ≦ x_i, y_i ≦100 的所有测试用例均得到正确回答 如果所有满足10点。 如果正确答案是满足
- N≦1,000 和 -1,000 ≦ x_i, y_i ≦1,000 的测试用例都被正确回答,则进一步 给出20点。总计30点。
- N≦10^5 和 -1,000 ≦ x_i, y_i ≦1,000 的测试用例都被正确回答,则进一步 给出30点。总计60点。
- N≦10^5 和 -10^5 ≦ x_i, y_i ≦10^5 的测试用例都被正确回答,则进一步 给出40点。总计100点。
出力
供水的花朵数量 输出为1行。在输出末尾插入换行符。
入力例1
2 0 1 0 -1
出力例1
9
如下图所示。绿点是接受水的花朵。红点是世界上最大的花所在的位置。 绿色和红色总计 有9。
入力例2
2 3 1 1 4
出力例2
74
如下图所示。 有
入力例3
4 3 4 4 3 -2 -2 -3 2
出力例3
146
如下图所示。 有