ZeroJudge 解題筆記：m685. 三角形計數器

作者：王一哲
日期：2025年12月6日


ZeroJudge 題目連結：m685. 三角形計數器

解題想法

這題要找共有幾組邊長比例不同的三角形。我是將讀到的一個三角形邊長由小到大排序，再用三個邊長的最大公因數約分，最後將約分後的邊長組成 tuple 或 vector 存進 set。讀取完所有測資之後，set 的大小就是答案。

Python 程式碼

使用時間約為 0.6 s，記憶體約為 23.9 MB，通過測試。

import math

n = int(input())
triangle = set()
for _ in range(n):
    a, b, c = sorted(list(map(int, input().split())))
    g = math.gcd(a, math.gcd(b, c))
    a, b, c = a//g, b//g, c//g
    triangle.add((a, b, c))
print(len(triangle))

C++ 程式碼

使用時間約為 0.1 s，記憶體約為 8.7 MB，通過測試。

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    set<vector<int>> triangle;
    for(int i=0; i<n; i++) {
        int edges[3];
        for(int j=0; j<3; j++) scanf("%d", &edges[j]);
        sort(edges, edges+3);
        int a = edges[0], b = edges[1], c = edges[2];
        int g = __gcd(a, __gcd(b, c));
        a /= g; b /= g; c /=g;
        triangle.insert({a, b, c});
    }
    printf("%ld\n", triangle.size());
    return 0;
}