日期：2026年4月9日
ZeroJudge 題目連結：d094. 00478 - Points in Figures: Rectangles and Circles, and Triangles
解題想法
這題是 d093. 00477 - Points in Figures: Rectangles and Circles 的加強版，除了長方形、圓形之外還多了三角形，可以用上一題的程式碼為基礎，再加上檢查點是否在三角形內的自訂函式。 假設平面上的三角形 ABC 頂點座標分別為 $(x_A, y_A), (x_B, y_B), (x_C, y_C)$，如果要判斷平面上的點 P $(x_P, y_P)$ 是否在三角形之中，P 點座標可以表示為 $$ P = uA + vB + wC $$ 解聯立後可得 $$ \begin{align*} u &= \frac{(x_B - x_A)(y_P - y_A) - (y_B - y_A)(x_P - x_A)}{(x_B - x_A)(y_C - y_A) - (y_B - y_A)(x_C - x_A)}\\ v &= \frac{(x_C - x_A)(y_P - y_A) - (y_C - y_A)(x_P - x_A)}{(x_C - x_A)(y_B - y_A) - (y_C - y_A)(x_B - x_A)} \\ w &= 1 - u - v & \end{align*} $$ 係數符合的條件為
- $0 \leq u \leq 1$
- $0 \leq v \leq 1$
- $0 \leq w \leq 1$
Python 程式碼
使用時間約為 9 ms，記憶體約為 8.6 MB，通過測試。
import sys
def in_rectangle(x, y, x1, y1, x2, y2):
"""
代入要測試的點座標 (x, y)
長方形左上頂點座標 (x1, y1)
長方形右下頂點座標 (x2, y2)
判斷點是否在長方形內
"""
if x1 < x < x2 and y1 > y > y2: return True
return False
def in_circle(x, y, xc, yc, r):
"""
代入要測試的點座標 (x, y)
圓心座標 (xc, yc)、半徑 r
判斷點是否在圓形內
"""
if (x-xc)**2 + (y-yc)**2 < r**2: return True
return False
def in_triangle(x, y, xA, yA, xB, yB, xC, yC):
"""
代入要測試的點座標 (x, y)
三角形頂點座標 (xA, yA), (xB, yB), (xC, yC)
判斷點是否在三角形內
"""
u = ((xB - xA)*(y - yA) - (yB - yA)*(x - xA)) / ((xB - xA)*(yC - yA) - (yB - yA)*(xC - xA))
v = ((xC - xA)*(y - yA) - (yC - yA)*(x - xA)) / ((xC - xA)*(yB - yA) - (yC - yA)*(xB - xA))
w = 1 - u - v
if 0 <= u <= 1 and 0 <= v <= 1 and 0 <= w <= 1: return True
return False
""" 讀取形狀 """
figures = [[]]
for line in sys.stdin:
if line.strip() == "*": break
data = line.split()
if data[0] == "r":
figures.append([0] + list(map(float, data[1:])))
elif data[0] == "c":
figures.append([1] + list(map(float, data[1:])))
else:
figures.append([2] + list(map(float, data[1:])))
""" 判斷點是否在圖形內並組合答案 """
result = []
i = 0
n = len(figures)
for line in sys.stdin:
if line.strip() == "9999.9 9999.9": break
i += 1
state = False
x, y = map(float, line.split())
for j in range(1, n):
if figures[j][0] == 0:
if in_rectangle(x, y, figures[j][1], figures[j][2], figures[j][3], figures[j][4]):
result.append(f"Point {i:d} is contained in figure {j:d}\n")
state = True
elif figures[j][0] == 1:
if in_circle(x, y, figures[j][1], figures[j][2], figures[j][3]):
result.append(f"Point {i:d} is contained in figure {j:d}\n")
state = True
else:
if in_triangle(x, y, figures[j][1], figures[j][2], figures[j][3], figures[j][4], figures[j][5], figures[j][6]):
result.append(f"Point {i:d} is contained in figure {j:d}\n")
state = True
if not state:
result.append(f"Point {i:d} is not contained in any figure\n")
sys.stdout.write("".join(result))
