問題描述

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

輸入格式

輸入共?n+1?行。

第一行為一個正整數?n。

后面?n?行，每行兩個整數?xi?,?yi??表示第 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≤xi,yi≤。

因為每個點橫縱坐標都是整數不會出現等邊三角形這種情況

枚舉每一個點作為頂點，所有與該頂點距離相等的點均位于以該頂點為圓心、以該距離為半徑的圓周上

觀察所有與該頂點距離相等的點是否有對稱點，除去三點共線的情況，并且這一條線會被記錄兩次，所以在答案我們要去掉cnt/2

解釋?ans += mp[d];?：

與頂點距離相同的點有2個點時，能構成1個等腰三角形

與頂點距離相同的點有3個點時，能構成3個等腰三角形 （+2）

與頂點距離相同的點有4個點時，能構成6個等腰三角形（+3）

與頂點距離相同的點有5個點時，能構成10個等腰三角形（+4）

求一個點在圓上關于圓心的對稱點：

#include<iostream>
#include<set>  // 包含 set
#include<map>  // 包含 map
using namespace std;const int N = 2e3+10; 
int n;
int ans;
int x[N], y[N];set<pair<int, int>>s;  //存儲所有點的坐標
map<int, int>mp;//計算i, j兩點間距離的平方
//使用平方距離避免浮點數運算
int dis(int i, int j)
{return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}int main()
{cin>>n;for(int i=1; i<=n; ++i){cin>>x[i]>>y[i];s.insert({x[i], y[i]});}//枚舉每個點作為等腰三角形的頂點for(int i=1; i<=n; ++i){int cnt=0;  //記錄共線三點的情況出現的次數//對于每個頂點i，遍歷所有其他點jfor(int j=1; j<=n; ++j){//確保不把頂點自己和自己比較if(i!=j){int d=dis(i, j);ans += mp[d]; //之前已經有mp[d]個點到 i 的距離也是 dmp[d]++;  //更新該距離的點數//檢查共線情況int x2=2*x[i]-x[j];  //計算對稱點x坐標int y2=2*y[i]-y[j];  //計算對稱點y坐標	            if(s.count({x2,y2}))cnt++;  //如果對稱點存在，則三點共線}}ans-=cnt/2;  //每對對稱點會被統計兩次mp.clear();  //清空mp，準備下一個頂點的統計}cout<<ans;return 0;
}