問題描述

小明在二維坐標系中放置了 n 個點，他想從中選出一個包含三個點的子集，使得這三個點能夠組成一個三角形。

由于這樣的方案太多了，他決定只選擇那些可以組成等腰三角形的方案。

請幫他計算出一共有多少種選法可以組成等腰三角形。

---

輸入格式

共 n + 1 行：

• 第 1 行：一個正整數 n，表示點的數量。
• 接下來的 n 行：每行兩個整數 x?、y?，表示第 i 個點的坐標。

---

輸出格式

輸出 1 行，一個整數，表示可以組成等腰三角形的選法數量。

---

樣例輸入

5
1 1
4 1
1 0
2 1
1 2

---

樣例輸出

4

---

樣例說明

一共有 4 種選法可以組成等腰三角形：

• {3, 4, 5}
• {1, 3, 4}
• {5, 2, 3}
• {1, 4, 5}

---

評測用例規模與約定

• 對于 20% 的數據，保證 n ≤ 200
• 對于 100% 的數據，保證：
  • n ≤ 2000
  • 0 ≤ x?, y? ≤ 10?

c++代碼

#include<bits/stdc++.h>
#include<math.h>using namespace std;typedef long long ll;ll n, ans = 0;
vector<vector<ll>> arr;
unordered_map<ll, vector<ll>> mp;ll delta(ll x1, ll y1, ll x2, ll y2) {return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}int main() {scanf("%lld", &n);arr = vector<vector<ll>>(n, vector<ll>(2));for (ll i = 0; i < n; i++) {scanf("%lld %lld", &arr[i][0], &arr[i][1]);}for (ll i = 0; i < n; i++) {mp.clear();for (ll j = 0; j < n; j++) {if (j == i) continue;ll d = delta(arr[i][0], arr[i][1], arr[j][0], arr[j][1]);vector<ll> mid = mp[d];for (ll k = 0; k < mid.size(); k++) {if (4 * d > delta(arr[j][0], arr[j][1], arr[mid[k]][0], arr[mid[k]][1])) ans++;}mp[d].push_back(j);}}printf("%lld", ans);return 0;
}//by wqs

這個題目需要注意三點共線的情況，要把這種情況舍去