# APCS實作題2016年10月第1題：三角形辨別
> 第1版：2023年2月10日
> 第2版：2023年6月5日，新增 C++ 程式碼以及不使用 sort 的寫法
> 作者：王一哲
> 題目來源：[105年10月29日實作題第1題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2020/11/1051029APCSImplementation.pdf)
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=c294)
<br />
## 題目
### 問題描述
三角形除了是最基本的多邊形外，亦可進一步細分為鈍角三角形、直角三角形及銳角三角形。若給定三個線段的長度，透過下列公式的運算，即可得知此三線段能否構成三角形，亦可判斷是直角、銳角和鈍角三角形。
提示：若a、b、c為三個線段的邊長，且c為最大值，則
- 若 $a + b \leq c$，三線段無法構成三角形
- 若 $a^2 + b^2 < c^2$，三線段構成鈍角三角形（Obtuse triangle）
- 若 $a^2 + b^2 = c^2$，三線段構成直角三角形（Right triangle）
- 若 $a^2 + b^2 > c^2$，三線段構成銳角三角形（Acute triangle）
請設計程式以讀入三個線段的長度判斷並輸出此三線段可否構成三角形？若可，判斷並輸出其所屬三角形類型。
<br />
### 輸入格式
輸入僅一行包含三正整數，三正整數皆小於30,001，兩數之間有一空白。
<br />
### 輸出格式
輸出共有兩行，第一行由小而大印出此三正整數，兩數字之間以一個空白間格，最後一個數字後不應有空白；第二行輸出三角形的類型：
- 若無法構成三角形時輸出「No」；
- 若構成鈍角三角形時輸出「Obtuse」；
- 若直角三角形時輸出「Right」；
- 若銳角三角形時輸出「Acute」。
<br />
### 範例一：輸入
```
3 4 5
```
### 範例一：正確輸出
```
3 4 5
Right
```
（說明）$a^2 + b^2 = c^2$ 成立時為直角三角形。
<br />
### 範例二：輸入
```
101 100 99
```
### 範例二：正確輸出
```
99 100 101
Acute
```
（說明）邊長排序由小到大輸出，$a^2 + b^2 > c^2$ 成立時為銳角三角形。
<br />
### 範例三：輸入
```
10 100 10
```
### 範例三：正確輸出
```
10 10 100
No
```
（說明）由於無法構成三角形，因此第二行須印出「No」。
<br />
### 評分說明
輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 2 秒，依正確通過測資筆數給分。其中，
- 第 1 子題組 10 分，整個家族的祖先最多 2 個小孩，其他成員最多一個小孩，$2 \leq n \leq 100$。
- 第 2 子題組 30 分，$2 \leq n \leq 100$。
- 第 3 子題組 30 分，$101 \leq n \leq 2,000$ 。
- 第 4 子題組 30 分，$1,001 \leq n \leq 100,000$。
<br />
## 分析
問題當中的提示，就是高中數學課程裡的餘弦定理，若a、b的夾角為 $\theta$，第三邊的長度為c，則
$$
c^2 = a^2 + b^2 - 2ab \cos \theta ~\Rightarrow~ \cos \theta = \frac{a^2 + b^2 - c^2}{2ab}
$$
有以下4種狀況
1. $-1 < \cos \theta < 0$：鈍角三角形
2. $\cos \theta = 0$：直角三角形
3. $0 < \cos \theta < 1$：銳角三角形
4. 其它狀況：無法形成三角形
<br /><br />
## Python 程式碼
### 方法1，使用最原始的方法排序
```python=
a, b, c = map(int, input().split())
# 將 a, b, c 由小到大排序
if a > b: a, b = b, a
if b > c: b, c = c, b
if a > b: a, b = b, a
print(a, b, c)
# 印出三角形種類
if a + b <= c:
print("No")
elif a**2 + b**2 < c**2:
print("Obtuse")
elif a**2 + b**2 == c**2:
print("Right")
elif a**2 + b**2 > c**2:
print("Acute")
```
<br />
1. 第1行：由標準輸入讀取3個數字，分別指定給變數 a、b、c。
2. 第3 ~ 5行：用最原始的方法由小到大排序，第3、4行執行後，最大值為c；第5行執行後，最小值為a。
3. 第6行：印出由小到大排序後的邊長。
4. 第9 ~ 16行：依照題目的提示，由 a、b、c 的關係判斷三角形的種類。
5. 於 ZeroJudge 測試結果，費時約 37 ms，使用記憶體 3.3 MB。
<br /><br />
### 方法2，使用 sort 排序
```python=
data = list(map(int, input().split()))
data.sort()
a, b, c = data[0], data[1], data[2]
print(a, b, c)
# 印出三角形種類
if a + b <= c:
print("No")
elif a**2 + b**2 < c**2:
print("Obtuse")
elif a**2 + b**2 == c**2:
print("Right")
elif a**2 + b**2 > c**2:
print("Acute")
```
<br />
1. 第1行：由標準輸入讀取3個數字，儲存到串列 data。
2. 第2行：使用 Python 內建的排序工具，預設是由小到大排序，如果要從大小到排序，程式碼要改為 **data.sort(reverse=True)**。
3. 第3行：將串列 data 的元素依序指定給變數 a、b、c。
4. 第4行：印出由小到大排序後的邊長。
5. 第7 ~ 14行：依照題目的提示，由 a、b、c 的關係判斷三角形的種類；如果要使用餘弦定理，程式碼改為
```python
d = (a**2 + b**2 - c**2)/(2*a*b)
if d > -1.0 and d < 0:
print("Obtuse")
elif d == 0:
print("Right")
elif d < 1.0 and d > 0:
print("Acute")
else:
print("No")
```
6. 於 ZeroJudge 測試結果，費時約 19 ms，使用記憶體 3.3 MB。
<br /><br />
## C++ 程式碼
### 方法1，使用最原始的方法排序
```cpp=
#include <iostream>
using namespace std;
int main(int argc, char *argv[]) {
int a, b, c, t;
cin >> a >> b >> c;
if (a > b) {
t = a; a = b; b = t;
}
if (b > c) {
t = b; b = c; c = t;
}
if (a > b) {
t = a; a = b; b = 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 if (a*a + b*b > c*c) {
cout << "Acute" << endl;
}
return 0;
}
```
<br />
1. 第5行：定義整數變數 a、b、c、t。
2. 第6行：由標準輸入讀取3個數字，分別指定給變數 a、b、c。
3. 第7 ~ 15行：用最原始的方法由小到大排序，第7 ~ 12行執行後，最大值為c；第13 ~ 15行執行後，最小值為a。
4. 第16行：印出由小到大排序後的邊長。
5. 第18 ~ 26行：依照題目的提示，由 a、b、c 的關係判斷三角形的種類。
6. 於 ZeroJudge 測試結果，費時約 4 ms，使用記憶體 332 kB。
<br /><br />
### 方法2，使用 STL sort 函式排序
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int p, int q) {
return (p < q);
}
int main(int argc, char *argv[]) {
int data[3], a, b, c;
for(int i=0; i<3; i++) cin >> data[i];
sort(data, data+3, cmp);
a = data[0]; b = data[1]; c = data[2];
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 if (a*a + b*b > c*c) {
cout << "Acute" << endl;
}
return 0;
}
```
<br />
1. 第10行：定義長度為3的整數陣列 data 及3個變數 a、b、c。
2. 第11行：由標準輸入讀取資料，依序放入陣列 data。
3. 第12行：使用 C++ STL 函式庫 alogrithm 提供的排序工具 sort，將陣列 data 由小到大排序。由於這個函式預設是由小到大排序，可以刪除程式碼中第5 ~ 7行，並將第12行改為 **sort(data, data+3)**；如果想要由大到小排序，則自訂函式的第6行改為 **return (p > q)**。
4. 第14行：印出由小到大排序後的邊長。
5. 第16 ~ 24行：依照題目的提示，由 a、b、c 的關係判斷三角形的種類。
6. 於 ZeroJudge 測試結果，費時約 3 ms，使用記憶體 348 kB。
<br /><br />
---
###### tags:`APCS`、`C`、`C++`、`Python`
Sign in with Wallet
Connect another wallet