AT_arc022_4 [ARC022D] スプリンクラー

[problemUrl]: https://atcoder.jp/contests/arc022/tasks/arc022_4 高橋くんは世界でも有数の広さを誇るお花畑を管理しています。このお花畑には、世界でもっとも美しい花が $ 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) $が成り立つ

水が供給される花の個数を$ 1 $行で出力せよ。出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ 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 $点となる。 ### Sample Explanation 1 下図のようになる。緑色の点が水が供給される花である。赤色の点は世界一の花の位置である。 緑と赤は合計で$ 9 $個ある。 !\[\](/img/arc/022/4-1.png) ### Sample Explanation 2 下図のようになる。 !\[\](/img/arc/022/4-2.png) ### Sample Explanation 3 下図のようになる。 !\[\](/img/arc/022/4-3.png)