TopCoder 2016 TCO Algorithm Round 2C Easy. BearBall

問題

n個の点が与えられる。点iから点jへボールをパスしたい。ボールは真っ直ぐにしか飛ばせず、点aと点bの間に別の点があるときは点aから点bに直接ボールを投げることはできない。

点iから点jへのパスの最小回数をすべての(i,j)に対して計算し、その総和を求めよ。

• 1≦n≦1500

解法

始点を一つ決める。

その始点を端点とした半直線に着目したとき、もしその半直線に複数の点が乗っていたら、1点を除いて2手以上掛かる。

その直線との距離が最も小さい点を選びパスすれば、必ず 2 手でパスできる。

もしこのパス上に他の点があったら最小性に矛盾してしまう。

全部の点が一直線上に並んだ場合はこの手法が使えないので別の計算を行う。

---

点を gcd で割って map に入れておけば O(n² log n)。

久々に easy がすんなり解けた。