Editorial for 三角形辨別 (APCS 2016-10 初級)
簡潔題意
讀入三個正整數邊長(皆 \(\le 30000\)),輸出兩行:第一行把三個數由小而大印出(空白間隔、行末無空白);第二行判斷三線段構成哪種三角形——無法構成印 No、鈍角 Obtuse、直角 Right、銳角 Acute。(APCS 逐筆給分。)
先排序:一次搞定兩件需求
題目有兩個地方都在要求「順序」:第一行要由小而大輸出;而提示的公式開頭就寫明「且 \(c\) 為最大值」——四條判斷式全部建立在這個前提上。偏偏輸入不保證任何順序(範例 2 是 101 100 99、範例 3 是 10 100 10),所以動手判斷之前,先把三個數由小到大排好,兩件需求同時到位:排好之後第一行直接印,而 \(c\) 自動就是最大值。
排序三個數,正是 3.9〈排序三個整數〉做過的事——三次「比較,順序不對就交換」,交換用暫存變數三行完成:
if (a > b) {
int t = a;
a = b;
b = t;
}
if (a > c) {
int t = a;
a = c;
c = t;
}
if (b > c) {
int t = b;
b = c;
c = t;
}
前兩個 if 讓 a 比 b、c 都小(a 歸位成最小),第三個 if 再把 b、c 排好。(之後學到 7.6 會認識內建的 swap(a, b),一行就能取代暫存變數三行;再往後學到下冊的排序(11.4),把三邊改存進陣列還能直接 sort(a, a + 3); 一行排好——不過這題用上冊前三單元的知識就完全足夠。)
照提示逐條判斷:順序是關鍵
提示的四條規則要照由上而下的順序檢查:第一關永遠是「能不能構成三角形」,通過了才輪得到平方比較。這不是隨便排的——鈍角、直角、銳角的平方判斷式,只對「真的是三角形」的三邊有意義。如果你先比平方,範例 3(排序後 10 10 100)會因為 \(10^2 + 10^2 < 100^2\) 被印成 Obtuse,但它連三角形都不是。
另外注意「無法構成」的條件是 \(a + b \le c\),等號也算:\(a + b\) 恰好等於 \(c\) 時,兩條短邊會「攤平」貼在最長邊上,變成一直線(例如 1 1 2),不算三角形。
漏掉等號的版本丟到 ZeroJudge c294 也會過——這不代表 \(a + b < c\) 是對的,只代表那邊的測試資料沒測到它會出錯的地方(本站的測資就抓得到)。
通過只能說明「這批測試資料沒抓到你的錯」,不能說明程式正確。
還有一件考場上該養成的習慣:判斷式裡出現平方,先估一下會不會爆 int(2.9 的溢位)。這題邊長最大 \(30000\),平方是 \(9 \times 10^8\),兩個相加 \(1.8 \times 10^9\)——沒有超過 int 上限(約 \(2.1 \times 10^9\)),所以用 int 剛好安全。不想每次都算的話,把三個變數宣告成 long long 一定不會錯,這題兩種都對。
判斷的部分用一條 if / else if 鏈(3.5)由上而下寫,完整程式:
#include <iostream>
using namespace std;
int main() {
int a, b, c;
cin >> a >> b >> c;
// 3.9 的三次比較交換:由小到大排好,c 自動變成最大值
if (a > b) {
int t = a;
a = b;
b = t;
}
if (a > c) {
int t = a;
a = c;
c = t;
}
if (b > c) {
int t = b;
b = c;
c = t;
}
cout << a << " " << b << " " << c << endl; // 第一行:由小到大
if (a + b <= c) {
cout << "No" << endl; // 先確認構不構成三角形
} else if (a * a + b * b < c * c) {
cout << "Obtuse" << endl;
} else if (a * a + b * b == c * c) {
cout << "Right" << endl;
} else {
cout << "Acute" << endl;
}
return 0;
}
測過再交:範例少了一種輸出
第二行總共有四種可能的輸出,但三個範例只涵蓋了 Right、Acute、No——Obtuse 從頭到尾沒出現過,你的鈍角分支對不對,範例完全沒測到。自己補幾筆把四種輸出都親眼看過,順便把邊界踩一遍:
| 輸入 | 第一行 | 第二行 | 這一筆在測什麼 |
|---|---|---|---|
2 3 4 |
2 3 4 |
Obtuse |
範例缺的鈍角(\(4 + 9 < 16\)) |
1 1 2 |
1 1 2 |
No |
\(a + b\) 恰好等於 \(c\) 的攤平情形 |
30000 30000 30000 |
30000 30000 30000 |
Acute |
最大邊長:驗你的型態撐不撐得住平方 |
5 4 3 |
3 4 5 |
Right |
輸入亂序:第一行要排好、\(c\) 要真的是最大 |
四種輸出都親眼看過正確,這題就穩了。
常犯錯誤
- 判斷順序錯:先比平方、
No擺後面:範例 3(排序後10 10 100)會因為 \(100 + 100 < 10000\) 被印成Obtuse——它連三角形都不是。照提示由上而下寫,第一關永遠是 \(a + b \le c\)。 - 「無法構成」漏了等號:條件寫成 \(a + b < c\) 的話,
1 1 2這種恰好攤平的輸入會溜進平方判斷、被印成Obtuse。正確是 \(a + b \le c\)。 - 沒有先排序:\(c\) 不是最大值的話,四條判斷式全部失去意義;第一行也不會由小而大。範例就當場抓到——
101 100 99第一行原樣印出是錯的,10 100 10更會從No變成Acute。 - 平方的溢位沒估算過:這題塞得進
int是主文估算過才敢說的;邊長上限再大一點(例如 \(10^5\),平方相加約 \(2 \times 10^{10}\))就爆了。看到平方,先看範圍,不確定就用long long。 - 第一行行末多印一個空白:像主文那樣「數字之間」才放空白(
a << " " << b << " " << c),最後一個數字後直接換行。本站的評測其實對行末空白寬容,但題目明寫「最後一個數字後沒有空白」,而檢定現場的評測嚴不嚴格沒人跟你保證。 - 輸出字串拼錯:
No、Obtuse、Right、Acute,照題目逐字抄。