ABC 402のD問題 Line Crossingの感想戦

at_coder, python
目次

ABC 402 の D 問題 Line Crossing の感想戦。平行な直線は傾きが等しくなるが、傾きを計算するのではなく多角形を結ぶ円と接する場所を考えて分類する。この時平行となる接線は 2 ヶ所存在するので、余りを使うことで 1 つに集約した。

AtCoder 東京海上日動プログラミングコンテスト 2025（AtCoder Beginner Contest 402）のD 問題 Line Crossingの感想戦

問題

多角形の 2 つの頂点を通り直線が与えられ、交差する直線の数を回答する。

方法

まず交わらない直線＝並行となっている直線のグループを作成する。あとはその組み合わせを数える。

最初は、直線が通る頂点の xy 座標を三角関数を使って求め、その傾きから直線をグループ化しようと考えた。しかし、この方法は三角関数の誤差に苦しめられて誤答(WA)に終わりました。y=0 (dx=0)になる可能性を忘れてランタイムエラー(RE)にもなったし。

そこで座標を求めるのではなく、直線を移動させることを考えました。

直線(1, 5)と(2, 4)は、平行です。これを移動させて多角形を結ぶ円の接線を考えると、接線は直線が通る頂点の平均になっています。そこでこの値で直線を分類します。頂点の数が奇数の場合も接点が頂点とはならないが、この考え方で行ける。

sample

ただし直線(6, 8)は、(1, 5)と平行なので交差しませんが、平均が 7 となりこのままでは別のグループに分類されてしまいます。そこで頂点の数の 1/2 で割り、その余りを使って分類することで(6, 8)と(1, 5)を同じグループにできることに気が付きました。

ただしここで平均を取るためと平行になる場所が 2 ヶ所あるので、それぞれ 2 で割っています。そのためこれを整理すると、2 で割る必要はなくなります。通る頂点の番号を加算して、頂点の数で割った値を使用するだけでよくなります。その結果、出てくる値が全て整数になります。これは Python は気にする必要がありませんが、静的型付け言語では助かります。

技術的工夫

defaultdictを使用することで、キーがすでに存在するかを考えなくて済むようにしました。

rom collections import defaultdict

n, m = map(int, input().split())

# mod = n / 2

grp = defaultdict(lambda: 0)
for _ in range(m):
    a, b = map(int, input().split())
    # ab = ((a + b) / 2) % mod
    ab = (a + b) % n
    # ab = ((a + b - 2) / 2) % mod # = ((a - 1 + b - 1) / 2) % mod
    # print(f"({a}, {b}) -> {ab}")
    grp[ab] += 1

crossing = 0
_m = m
for v in grp.values():
    crossing += v * (_m - v)
    _m -= v
print(crossing)