ABCを解いた【垂直二等分線】

筆者はレート800前後の茶～緑コーダ

ABC467のD問題を解いていく

実装コード

2点から作る垂直二等分線を正規化し、2本が交わるか同じ直線なら Yes と判定する。

• gcd は直線の係数を共通の約数で割るために使う
• get_canonical(px, py, qx, qy) で、点 (px, py) と (qx, qy) の垂直二等分線を ax + by + c = 0 の形にする
• 係数 a, b, c を g で割り、同じ直線なら同じタプルになるように正規化する
• a < 0 や a == 0 and b < 0 の場合は符号を反転し、直線の向きをそろえる
• 各テストケースで PQ と RS から、それぞれ垂直二等分線 (a1, b1, c1) と (a2, b2, c2) を作る
• a1 * b2 - a2 * b1 == 0 なら2本の直線は平行なので、同じ直線なら Yes、別の直線なら No を出力する
• 平行でなければ2本の直線は交点を持つので Yes を出力する

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def get_canonical(px, py, qx, qy):
    a = 2 * (qx - px)
    b = 2 * (qy - py)
    c = px * px + py * py - qx * qx - qy * qy
    g = gcd(a, gcd(b, c))
    a //= g
    b //= g
    c //= g

    if a < 0 or (a == 0 and b < 0):
        a = -a
        b = -b
        c = -c

    return a, b, c


def main():
    T = rI()

    for _ in range(T):
        px, py, qx, qy, rx, ry, sx, sy = rLI()

        a1, b1, c1 = get_canonical(px, py, qx, qy)
        a2, b2, c2 = get_canonical(rx, ry, sx, sy)

        if a1 * b2 - a2 * b1 == 0:
            if (a1, b1, c1) == (a2, b2, c2):
                print('Yes')
            else:
                print('No')
        else:
            print('Yes')


if __name__ == '__main__':
    main()

感想

垂直二等分線を直線の交点判定に落とす発想が勉強になった。
係数を gcd で正規化して、同一直線かどうかをタプルで比較できるようにする発想が必要だと思った。