#题解# F等腰三角形(hard)

省流： 计算贡献。考虑如何减去三点一线，当且仅当三点一线 $a, b, c$ , 且 $a b = b c$ 时会产生贡献，我们枚举 $a$ 和 $c$ , 通过中点公式得到中点 $m$ , 只需要判断点 $m$ 是否在 $n$ 里面出现过就行。这一部分答案记为 $c n t$ 。

对于所有合法等腰+非法的答案 $a n s$ , 我们通过枚举两点, 确定所有边, 并存入 $E d g e$ , 对于所有边我们记录他的一个端点和长度。对 $E d g e$ 双关键字排序后, 扫一遍, 我们就可以知道任意具有公共交点长度相同的边的重复次数 p, 那么一种 $p$ 对答案的贡献就是 $C (p, 2)$ 。

(例如, 与点 $1$ 一共有四条边相连, 他们的长度(不开方)为 $4 、 5 、 4 、 8$ , 我们 sort 以后就是 $(1, 4), (1, 4), (1, 5), (1, 8)$ 扫一遍可以知道点 $1$ 对答案的贡献就是那两条相同长度的边, 对答案的贡献就是 $C(2,2)。换言之, 通过考虑边而非考虑点, 我们既要使得两边长度相同, 又要考虑他们有公共交点。)

最终的答案就是 $a n s - c n t$ 。

我们用 $s t [x + 502] [y + 502]$ 判断 $(x, y)$ 是否出现。为了避免浮点数, 我们不对边长开方, 最大的长度为 $(1000\sqrt2)^2$ , 所以我们并不需要开 $long\,\,long$ (悲）

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>

using i32 = int32_t ;
using T = std::vector<int> ;

constexpr int STEP = 502; 

i32 main() {
	
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int n; std::cin>>n;
	std::vector<std::array<i32, 2>> Qir(n+3); 
	
	std::vector<std::vector<bool>> st(1145, std::vector<bool> (1145));
	
	auto push = [&](i32 x, i32 y) {
		st[x+STEP][y+STEP] = 1;
	};
	
	auto ck = [&](i32 x, i32 y) -> bool {
		return st[x+STEP][y+STEP];
	};
	
	for (int i=1;i <= n;i ++ ) {
		
		i32 x, y; std::cin>>x>>y;
		Qir[i] = {x, y};
		push(x, y); // 存点 
	}
	
	auto get = [&](auto& x, auto& y) -> i32{
		return ((i32)x[0]-y[0])*((i32)(x[0]-y[0])) + ((i32)(x[1]-y[1]))*((i32)(x[1]-y[1]));
	};
	
	std::vector<std::pair<i32, i32>> Edge; // <pos, len> 
	for (int i=1;i <= n;i ++ ) {
		for (int j=1;j <= n;j ++ ) {
			if (i == j) continue ;
			
			i32 eg = get(Qir[i], Qir[j]);
			Edge.push_back({i, eg});
		}
	}
	
	// 三点共线且a = b
	i32 cnt = 0;
	for (int i=1;i <= n;i ++ ) {
		for (int j=i+1;j <= n;j ++ ) {
			i32 mx = Qir[i][0]+Qir[j][0];
			i32 my = Qir[i][1]+Qir[j][1];
			
			if (mx%2 || my%2) continue ;
			mx /= 2, my /= 2;
			if (ck(mx, my)) cnt ++ ;
		}
	} 
	
	sort(Edge.begin(), Edge.end(), [&](auto& x, auto& y) -> bool{
		if (x.first != y.first) return x.first<y.first;
		return x.second<y.second;	
	});
	
	Edge.push_back({0, 0}); // 计算最后的lp, lc情况
	
	auto eval = [&](i32 x) ->i32{
		return (x>=2)?(x*(x-1)/2):0;
	};
	
	i32 ans = 0;
	i32 lp = 0, lt = 0; // last_pos, last_length 
	i32 c = 0;
	
	for (int i=0;i < Edge.size();i ++ ) {
		
		i32 pos = Edge[i].first;
		i32 len = Edge[i].second;
		 
		if (pos == lp && lt == len ) {
			c ++ ;
		} else { 
			ans += eval(c);
			c = 1, lt = len, lp = pos; // 注意 c=1
		} 
	}
	
	std::cout<<ans-cnt<<"\n"; 
	return 0;
}