牛客小白月赛69补题——F题

  发挥得比较好的一场，成功上蓝名了hh，截图纪念一下~

题目链接：
https://ac.nowcoder.com/acm/contest/52441/F?&headNav=acm

关键结论：
  格点图中不存在坐标均为整数的等边三角形。

核心思想：
  枚举等腰三角的的顶点 $P$，然后统计其它点到 $P$ 距离相等的数量，通过开桶的方式来统计，做到不重不漏。

AC代码：

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef pair<int, int> PII;
const int N = 2e6 + 10;
int cnt[N];
bool st[3010][3010];
PII a[3010];
int n, line, ans;

int get_dis(int i, int j){
	int dx = a[i].x - a[j].x, dy = a[i].y - a[j].y;
	return dx * dx + dy * dy;
}

void solve(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d%d", &a[i].x, &a[i].y);
		st[a[i].x + 1500][a[i].y + 1500] = true;
	}
	
	for(int i = 1; i <= n; i++){  //枚举i作为等腰三角形的顶点 
		for(int j = 1; j <= n; j++){
			if(i == j) continue;
			ans += cnt[get_dis(i, j)];
			cnt[get_dis(i, j)]++;
			if(st[2 * a[i].x - a[j].x + 1500][2 * a[i].y - a[j].y + 1500]) line++;
		}
		for(int j = 1; j <= n; j++){
			if(i == j) continue;
			cnt[get_dis(i, j)] = 0;
		}
	}
	printf("%d\n", ans - line / 2);
}

int main(){
	int T = 1;
//	scanf("%d", &T);
	while(T -- ) {
		solve();
	}
	
	return 0;
}