AtCoder Regular Contest 022

D - スプリンクラー


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋くんは世界でも有数の広さを誇るお花畑を管理しています。このお花畑には、世界でもっとも美しい花が 1 輪だけ咲いています。 このお花畑の中の点はその世界一の花からの距離で表します。その花から東に x ,南に y 移動した点の位置を (x, y) と表します。 高橋くんは非常に几帳面なので、 xy が共に整数であるような点 (x, y) には必ず 1 輪の花を植えています。そこ以外には植えていません。

より形式的に言うと、直交座標上の全ての格子点の上に 1 輪の花が植えられていて、原点には世界一の花が植えられています。格子点以外の点に花は植えられていません。

世界一の花は、大量の水を必要とします。そういうわけで高橋くんはお花畑のなかの N 箇所にスプリンクラーを設置することにしました。 どのスプリンクラーも xy も整数であるような点 (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

下図のようになる。


Submit提出する