← 返回题目列表

AtCoder · arc022_4

D. 洒水器

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

問題文

高桥君管理着世界上最大的花园之一。这个花园里有世界上最美丽的花朵。 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

如下图所示。 有