题目链接
题意
二维平面上有$n$个点，问你这些点能组成多少个正多边形。
思路
观察一下就可以发现，除了正四边形整数点不可能构成其他多边形，所以我们只需要找有多少个正四边形。
注意这个题的四边形其实可以是斜着的，所以我们不能只枚举左下角。需要枚举至少两个点。
我的方法是枚举其中两个点，这两个点会构成一个向量$(dx,dy)$，有一个可能的正方形是这样的:$(0,0),(dx,dy),(-dy,dx),(dx-dy,dx+dy).$
我们去看是否这四个点都存在，如果存在记录答案，最后答案除以4，因为每个正方形的4条边都被计算了一次。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using namespace std;
typedef long long ll;
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
const int N = 205;
int mov[3][2]={{0,1},{1,0},{1,1}};
bool has[210][210];
vector<pair<int, int> > v;
int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
for (int i = 0; i <= 209; i++)
for (int j = 0; j <= 209; j++)
has[i][j] = 0;
v.clear();
for (int i = 1; i <= n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
has[x + 100][y + 100] = true;
v.push_back(make_pair(x, y));
}
ll cnt = 0;
int sz=v.size();
for (int i=0;i<sz;i++)
{
int x=v[i].first,y=v[i].second;
for(int j=0;j<sz;j++){
int xx=v[j].first,yy=v[j].second;
if(j==i) continue;
int dx=xx-x,dy=yy-y;
int flag=1;
int dxx=x-dy,dyy=y+dx;
if(dxx<-100 || dxx>100 || dyy<-100 || dyy>100||!has[dxx+100][dyy+100]){
flag=0;
}
dxx=x-dy+dx,dyy=y+dx+dy;
if(dxx<-100 || dxx>100 || dyy<-100 || dyy>100||!has[dxx+100][dyy+100]){
flag=0;
}
cnt+=flag;
}
}
printf("%lld\n",cnt / 4);
}
return 0;
}