MediumRating 1436

2001. Number of Pairs of Interchangeable Rectangles

arrayhash-tablemathcountingnumber-theory

解題說明

Number of Pairs of Interchangeable Rectangles

題目描述：給定 n 個矩形，每個矩形以 [width, height] 表示。兩個矩形「可互換」的條件是它們的寬高比相同，即 width_i / height_i == width_j / height_j。求可互換的矩形對數。

解題思路：

為避免浮點數精度問題，將寬高比化為最簡分數：對每個矩形求 gcd(width, height)，然後用 (width/gcd, height/gcd) 作為鍵。
使用雜湊表統計每種最簡分數的矩形數量。
對於每個分組中有 c 個矩形，可組成 c * (c - 1) / 2 對。
將所有分組的配對數相加即為答案。

C++ 解法

複雜度分析

時間複雜度：O(n log M) — 遍歷所有矩形，每個求 gcd 需要 O(log M)（M 為寬高最大值）。

空間複雜度：O(n) — 雜湊表最多儲存 n 個不同的比例。

虛擬碼

1. Create hash map: (reduced_width, reduced_height) -> count
2. For each rectangle (w, h):
   a. g = gcd(w, h)
   b. Increment map[(w/g, h/g)]
3. For each group with count c:
   a. Add c * (c - 1) / 2 to answer
4. Return answer

其他解法

浮點數法 O(n)：直接用 double 型別計算 width / height 作為鍵。簡單但有精度風險，不建議在大數值場景使用。

排序法 O(n log n)：將所有矩形按最簡分數排序，然後線性掃描計數連續相同分數的數量。時間複雜度略高但不需雜湊表。

延伸思考

如果改為三維長方體 [l, w, h]，兩個長方體可互換的條件是比例完全相同，做法如何推廣？
如何避免整數溢出？（提示：當 c 很大時 c*(c-1) 可能溢出）
如果矩形的寬和高可以為浮點數，如何處理精度問題？