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;
}

前兩個 ifabc 都小(a 歸位成最小),第三個 if 再把 bc 排好。(之後學到 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),不算三角形。

在 OJ 上過了,不等於程式是對的

漏掉等號的版本丟到 ZeroJudge c294 也會過——這不代表 \(a + b < c\) 是對的,只代表那邊的測試資料沒測到它會出錯的地方(本站的測資就抓得到)。

通過只能說明「這批測試資料沒抓到你的錯」,不能說明程式正確。

還有一件考場上該養成的習慣:判斷式裡出現平方,先估一下會不會爆 int2.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;
}

測過再交:範例少了一種輸出

第二行總共有四種可能的輸出,但三個範例只涵蓋了 RightAcuteNo——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\) 要真的是最大

四種輸出都親眼看過正確,這題就穩了。

常犯錯誤
  1. 判斷順序錯:先比平方、No 擺後面:範例 3(排序後 10 10 100)會因為 \(100 + 100 < 10000\) 被印成 Obtuse——它連三角形都不是。照提示由上而下寫,第一關永遠是 \(a + b \le c\)。
  2. 「無法構成」漏了等號:條件寫成 \(a + b < c\) 的話,1 1 2 這種恰好攤平的輸入會溜進平方判斷、被印成 Obtuse。正確是 \(a + b \le c\)。
  3. 沒有先排序:\(c\) 不是最大值的話,四條判斷式全部失去意義;第一行也不會由小而大。範例就當場抓到——101 100 99 第一行原樣印出是錯的,10 100 10 更會從 No 變成 Acute
  4. 平方的溢位沒估算過:這題塞得進 int 是主文估算過才敢說的;邊長上限再大一點(例如 \(10^5\),平方相加約 \(2 \times 10^{10}\))就爆了。看到平方,先看範圍,不確定就用 long long
  5. 第一行行末多印一個空白:像主文那樣「數字之間」才放空白(a << " " << b << " " << c),最後一個數字後直接換行。本站的評測其實對行末空白寬容,但題目明寫「最後一個數字後沒有空白」,而檢定現場的評測嚴不嚴格沒人跟你保證。
  6. 輸出字串拼錯NoObtuseRightAcute,照題目逐字抄。