日期：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))
C++ 程式碼
2025年7月27日測試，使用時間約為 3 ms，記憶體約為 284 kB，通過測試。2026年4月6日測試，使用時間約為 1 ms，記憶體約為 3 MB，通過測試。
#include <cstdio>
#include <vector>
using namespace std;
bool in_rectangle(double x, double y, double x1, double y1, double x2, double y2) {
/* 代入要測試的點座標 (x, y)
長方形左上頂點座標 (x1, y1)
長方形右下頂點座標 (x2, y2)
判斷點是否在長方形內 */
if (x > x1 && x < x2 && y < y1 && y > y2) return true;
return false;
}
bool in_circle(double x, double y, double xc, double yc, double r) {
/* 代入要測試的點座標 (x, y)
圓心座標 (xc, yc)、半徑 r
判斷點是否在圓形內 */
if ((x-xc)*(x-xc) + (y-yc)*(y-yc) < r*r) return true;
return false;
}
bool in_triangle(double x, double y, double xA, double yA, double xB, double yB, double xC, double yC) {
/* 代入要測試的點座標 (x, y)
三角形頂點座標 (xA, yA), (xB, yB), (xC, yC)
判斷點是否在三角形內 */
double u = ((xB - xA)*(y - yA) - (yB - yA)*(x - xA)) / ((xB - xA)*(yC - yA) - (yB - yA)*(xC - xA));
double v = ((xC - xA)*(y - yA) - (yC - yA)*(x - xA)) / ((xC - xA)*(yB - yA) - (yC - yA)*(xB - xA));
double w = 1 - u - v;
if (u >= 0 && u <= 1 && v >= 0 && v <= 1 && w >= 0 && w <= 1) return true;
return false;
}
struct Obj {
char t;
double x1, y1, x2, y2, x3, y3, x4, y4;
};
int main() {
/* 讀取形狀 */
vector<Obj> figures (1);
char t; // 形狀的種類
while(scanf("%c", &t) != EOF && t != '*') {
if (t == 'r') {
Obj tmp;
tmp.t = 'r';
scanf("%lf %lf %lf %lf", &tmp.x1, &tmp.y1, &tmp.x2, &tmp.y2);
figures.push_back(tmp);
} else if (t == 'c') {
Obj tmp;
tmp.t = 'c';
scanf("%lf %lf %lf", &tmp.x1, &tmp.y1, &tmp.x2);
figures.push_back(tmp);
} else if (t == 't') {
Obj tmp;
tmp.t = 't';
scanf("%lf %lf %lf %lf %lf %lf", &tmp.x1, &tmp.y1, &tmp.x2, &tmp.y2, &tmp.x3, &tmp.y3);
figures.push_back(tmp);
}
}
/* 判斷點是否在圖形內並組合答案 */
int j = 0, n = (int)figures.size();
double x, y;
while(scanf("%lf %lf", &x, &y) != EOF) {
if (x > 9999.89 && x < 10000.01 && y > 9999.89 && y < 10000.01) break;
j++;
bool state = false;
for(int k=1; k<=n; k++) {
if (figures[k].t == 'r') {
if (in_rectangle(x, y, figures[k].x1, figures[k].y1, figures[k].x2, figures[k].y2)) {
printf("Point %d is contained in figure %d\n", j, k);
state = true;
}
} else if (figures[k].t == 'c') {
if (in_circle(x, y, figures[k].x1, figures[k].y1, figures[k].x2)) {
printf("Point %d is contained in figure %d\n", j, k);
state = true;
}
} else {
if (in_triangle(x, y, figures[k].x1, figures[k].y1, figures[k].x2, figures[k].y2, figures[k].x3, figures[k].y3)) {
printf("Point %d is contained in figure %d\n", j, k);
state = true;
}
}
}
if (!state) printf("Point %d is not contained in any figure\n", j);
}
return 0;
}
沒有留言:
張貼留言