問題
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) ) # 分割された多角形の数 # =線分と交差する多角形の辺の本数÷2+1 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)