C - Convex Quadrilateral Editorial by Tomii9273
問題文の条件のもとで、以下が成立します。
「四角形が凸である」
⇔「四角形の2本の対角線が交わる」
⇔「四角形の2本の対角線の両方において、対角線に使われない2点が対角線 (を延長した直線) の異なる側にある」
また、2点 \((x_0, y_0), (x_1, y_1)\) が直線 \(f(x, y) = 0\) の異なる側にあるかは、\(f(x_0, y_0)\) と \(f(x_1, y_1)\) の符号が異なるかを見ることで判定できます。
よって、2本の対角線それぞれについてこの判定を行うことで解くことができます。
なお、2点 \((x_0, y_0), (x_1, y_1)\) を通る直線の方程式として
\((x_1 - x_0)(y - y_0) = (y_1 - y_0)(x - x_0)\)
を使うと、場合分けの必要がありません。
実装例 (Python)
X = []
Y = []
for _ in range(4):
x, y = map(int, input().split())
X.append(x)
Y.append(y)
def f0(x, y): # 1 本目の対角線 (方程式の右辺が 0 になるようにした場合の左辺)
return (X[2] - X[0]) * (y - Y[0]) - (Y[2] - Y[0]) * (x - X[0])
def f1(x, y): # 2 本目の対角線 (方程式の右辺が 0 になるようにした場合の左辺)
return (X[3] - X[1]) * (y - Y[1]) - (Y[3] - Y[1]) * (x - X[1])
def sgn(x): # x の符号が正なら 1、負なら -1、0 なら 0 を返す
if x == 0:
return 0
return x // abs(x)
if sgn(f0(X[1], Y[1])) != sgn(f0(X[3], Y[3])) and sgn(f1(X[0], Y[0])) != sgn(f1(X[2], Y[2])):
print("Yes")
else:
print("No")
posted:
last update: