問題概要 平面上にN個の点があり、dist(p[i], p[i+1])が分かっている。dist(p[0], p[N-1])のとりうる最小値と最大値を求める問題。 解法 最大値は自明に和。最小値は存在しても必ず整数でもっとも長い辺をキャンセルするように作れば良い。

問題概要 最遠点対。 解法 O(N^2)で全探索間に合う。ちなみに凸包作ってキャリパー法でO(N*log N)。

結果。 3/4完。何がひどいって言語のバグで解けなかったのが辛い。D言語を諦めて安心と信頼のpythonで書き直したら通ったけど、残り時間がほとんどなくてD問題は諦めた。ちょっと見たときは、集合としての個数を数えるのだと思って難しそうだと思ってたけど…