alan23273850 的刷題筆記
b352: 相似
Tags: math
出處：https://zerojudge.tw/ShowProblem?problemid=b352
提交：https://zerojudge.tw/Submissions?problemid=b352&account=allllllan123456
問題：給你 $n\in[1,100000]$ 組三根棍子的長度 $\in\text{int}^+$，先問你這其中有幾組棍子可以自己組成一個 (面積為正的) 三角形，接著再繼續把彼此相似的三角形們合成一類，問你最大類的三角形個數少一是多少。
解法：首先，要判斷一組三角形邊長是否合法，必須先把棍子長由小到大排序，而且檢查兩小邊之和大於第三邊的時候必須轉成減法操作以免溢位。另外，對於每個三角形其實都存在唯一一個三邊長 $a,b,c$ 滿足 $a\le b\le c$ 且 $\gcd(a,b,c)=1$ 的三角形與之相似，我稱滿足上述條件的三角形為「最簡三角形」，事實上兩個三角形「相似」若且為若 (if and only if) 它們各自對應的最簡三角形「全等」，因此我只要想辦法把每個三角形都化成它們各自對應的最簡三角形，並且加以排序以確保彼此全等的三角形會相鄰，這樣就能知道最大類的相似三角形個數有多少了 (最後記得減一)。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 vector<tuple<int, int, int>> v; int n; cin >> n;
6 while (n--) { int a[3];
7 cin >> a[0] >> a[1] >> a[2];
8 sort(a, a+3);
9 if (a[0] > a[2] - a[1]) { // avoid overflow
10 int d = __gcd(__gcd(a[0], a[1]), a[2]);
11 a[0] /= d; a[1] /= d; a[2] /= d;
12 v.push_back(tuple<int, int, int>(a[0], a[1], a[2]));
13 }
14 }
15 sort(v.begin(), v.end()); // for grouping the similar triangles together
16 int max=0, count=0; tuple<int, int, int> before;
17 for (const auto &e: v)
18 if (e == before) {
19 count++;
20 if (count > max) max = count;
21 } else
22 before = e, count = 0;
23 cout << v.size() << ' ' << max << '\n';
24 return 0;
25}