[Python] ABC016 D

問題

D – 一刀両断

回答

以下が大変参考になりました。

直線と線分

import numpy as np

Ax, Ay, Bx, By = map(int, input().split())

N = int(input())
positions = [list(map(int, input().split())) for _ in range(N)]
# 一番最後に、最後の点と最初の点を結んだ線分を考える
positions.append(positions[0])

def is_intersected(a1, a2, b1, b2):
    """
    a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定
    """
    return \
    (
    (np.cross(a2-a1, b1-a1) * np.cross(a2-a1, b2-a1) < 0) 
    and
    (np.cross(b2-b1, a1-b1) * np.cross(b2-b1, a2-b1) < 0)
    )


# 分割された多角形の数 
# ＝線分と交差する多角形の辺の本数÷２＋１
a1 = np.array([Ax, Ay])
a2 = np.array([Bx, By])

cnt = 0
for i in range(N):
    b1 = np.array(positions[i])
    b2 = np.array(positions[i+1])
    
    if is_intersected(a1, a2, b1, b2):
        cnt += 1
    
print(cnt // 2 + 1)