Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋くんは世界でも有数の広さを誇るお花畑を管理しています。このお花畑には、世界でもっとも美しい花が 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
下図のようになる。