問題描述

小明在二維坐標系中放置了 ( n ) 個點，他想在其中選出一個包含三個點的子集，這三個點能組成三角形。然而這樣的方案太多了，他決定只選擇那些可以組成等腰三角形的方案。請幫他計算出一共有多少種選法可以組成等腰三角形？

輸入格式

輸入共 ( n+1 ) 行。

第一行為一個正整數 ( n )。

后面 ( n ) 行，每行兩個整數 ( x_i ) 和 ( y_i ) 表示第 ( i ) 個點的坐標。

輸出格式

輸出共 1 行，一個整數。

樣例輸入

5
1 1
4 1
1 0
2 1
1 2

樣例輸出

4

評測用例規模與約定

• 對于 20% 的數據，保證 ( n <= 200)。
• 對于 100% 的數據，保證 ( n <= 2000)，( 0 <= xi, yi <= 1e9)。

題解:

正常的暴力代碼👇 時間復雜度O(n^3) 會超時, 只過了不到一半數據

#include <bits/stdc++.h>
using namespace std;
#define int doubleconst signed N = 1e4;int a[N], b[N];signed main()
{signed n; cin >> n;for (signed i = 0; i < n; i ++) cin >> a[i] >> b[i];int cnt = 0;for (signed i = 0; i < n; i ++)for (signed j = i + 1; j < n;  j ++)for (signed k = j + 1; k < n; k ++){int x1 = sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));int x2 = sqrt((a[j] - a[k]) * (a[j] - a[k]) + (b[j] - b[k]) * (b[j] - b[k]));int x3 = sqrt((a[i] - a[k]) * (a[i] - a[k]) + (b[i] - b[k]) * (b[i] - b[k]));if (x1 + x2 > x3 && x1 + x3 > x2 && x2 + x3 > x1){if (abs(x1 - x2) < 1e-8 && abs(x2 - x3) < 1e-8 && abs(x1 - x3) < 1e-8) continue;  // 等邊三角形不算， 也可以不寫, 因為題中要求橫縱坐標都是整數, 那么不可能構成等邊三角形if (abs(x1 - x2) < 1e-8 || abs(x2 - x3) < 1e-8 || abs(x1 - x3) < 1e-8)  // double 類型判斷是否相同要用差來判斷, double類型的變量在計算機中存儲的值會丟失精度, 不能直接用==cnt ++;}}cout << cnt << endl;return 0;
}

---

ac代碼

這題的思路是盡可能優化時間復雜度,

• 我們枚舉每個點, 然后對該點生成一個hash表, 把到該點距離相同的點放到一個數組中, 然后遍歷這個hash表中的所有數組,任選數組中的兩個點, 判斷這三個點是否滿足條件

ac代碼👇 這個的時間復雜度是在O(n^2) 和 O(n^3)之間的

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y second
typedef pair<int, int> PII;
const double cha = 1e-8;
vector<PII> v;double dist(int x1, int y1, int x2, int y2)
{return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}bool check(PII a, PII b, PII c)
{double x1 = dist(a.x, a.y, b.x, b.y);double x2 = dist(a.x, a.y, c.x, c.y);double x3 = dist(b.x, b.y, c.x, c.y);if (x1 + x2 <= x3 || x1 + x3 <= x2 || x2 + x3 <= x1) return false;  // 不能構成三角形if (abs(x1 - x2) < cha && abs(x1 - x3) < cha && abs(x2 - x3) < cha) return false;  // 是等邊三角形。也可以不寫, 因為題中要求橫縱坐標都是整數, 那么不可能構成等邊三角形return true;
}signed main()
{int n; cin >> n; v.resize(n);for (int i = 0; i < n; i ++) cin >> v[i].x >> v[i].y;int cnt = 0;for (int i = 0; i < n; i ++){unordered_map<double, vector<int>> mp;  // 選用i為一個點的前提下, 其他點到i距離相同的點存放到一個 vector中for (int j = 0; j < n; j ++){if (i == j) continue;double dis = dist(v[i].x, v[i].y, v[j].x, v[j].y);  // 計算距離mp[dis].emplace_back(j);  }for (auto it : mp){vector<int> vv;vv = it.second;  // vv 是到i距離相同的點的 集合, 也就是說vv中的元素都是到i的距離相同的點for (int j = 0; j < vv.size(); j ++)for (int k = j + 1; k < vv.size(); k ++){if (check(v[i], v[vv[j]], v[vv[k]])) cnt ++;  // 因為vv里面存的是下標, 所以是 v[vv[j]]}}}cout << cnt << endl;return 0;
}

下面是筆者自己理解的ac代碼的時間復雜度的分析

hash時間復雜度分析:

中間的點在執行hash時是最耗時的, 而且圖中這種方式的點分布也是讓所有點的時間復雜度盡可能多的情況。

下面分別是vector的個數和map個數分析

• 因為坐標的橫縱坐標都只能是整數, 所有一個 map映射的vector中最多有4個數, 也就是說距離到i坐標相同的點最多有4個, 上下左右距離相同 4個, 4個對焦的點距離相同.

• 而map映射的個數是 中間的點的最外圍每增加一圈, map映射的個數加2, 因為每增加一圈 橫縱的距離+1, 斜線的距離+根號2， 一共是兩種

hash執行總次數 m 和總個數 n 之間的大小關系分析

當點的個數增加到2000的時候, 實際hash執行的次數不到2000 (map的映射個數不到 100,(這里按50個外圈, 50 * 50是2500個點的個數, 比2000個點大), vecotr中最多是4個點, 4 * 4 = 16) 所以hash執行的次數是100 * 16 == 1600, 這還是中間點的情況, 而且是按2500個點算, 其他點的遍歷次數更少 ( m < n )

還有就是, 從上面的分析可以看到, 點的個數越小, 遍歷hash的總次數有可能反而比 n 次還要多, 但是當點的個數n邊大的時候, 遍歷hash的總次數會比(n - 1)小很多。------> 比如一共9個點, 3*3, 中間的點正常應該遍歷(n - 1) = 8次, 但是用hash的話應該遍歷了 2 * (4 * (4 - 1) / 2) = 12次, 2是hash的兩個映射 距離為1和距離為根號2, 4是距離為1和根號2的vector中各有4各元素 。(ps:代碼中的for ( int j = 0; j < vv.size(); j ++);for (int k = j + 1; k < vv.size(); k ++) 時間復雜度是(n * (n - 1) / 2)

總的時間復雜度

當點的個數比較大的時候, O(n * (n + m)), m < n, 時間復雜度很OK
即使當點的個數n比較小的時候m可能比n大, 但無傷大雅, 因為它不會比n大特別多,而且也說了 n 比較小這個前提, 這個ac代碼的時候復雜度可以看成是O(n^2)

覺得寫的不錯的話, 點個贊吧~