2 条题解
-
0
四个点关于某点中心对称,显然就形成了一个广义的平行四边形(共线也算)。因此这四个点一定满足 (x1+x2=x3+x4,y1+y2=y3+y4)。 因此我们把所有的 (x1+x2,y1+y2) 合成一个 pair,再插入一个map或是哈希表内,即可通过扫描得到答案。 注意每一个平行四边形都要被算两次,因此答案要除以二。
#include <bits/stdc++.h> using namespace std; int n, ans, x[1005], y[1005]; map<pair<int, int>, int> p; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &x[i], &y[i]); } for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { p[make_pair(x[i] + x[j], y[i] + y[j])]++; } } for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { ans += p[make_pair(x[i] + x[j], y[i] + y[j])] - 1; } } printf("%d\n", ans / 2); return 0; } -
0
/* 四个点关于某点中心对称,显然就形成了一个广义的平行四边形(共线也算)。因此这四个点一定满足 x1+x2=x3+x4,y1+y2=y3+y4。 因此我们把所有的 x1+x2,y1+y2 合成一个 pair,再插入一个map或是哈希表内,即可通过扫描得到答案。 注意每一个平行四边形都要被算两次,因此答案要除以二。 */ #include<bits/stdc++.h> using namespace std; int n,ans,x[1005],y[1005]; map<pair<int,int>,int>p; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&x[i],&y[i]); } for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++){ p[make_pair(x[i]+x[j],y[i]+y[j])]++; } } for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++){ ans+=p[make_pair(x[i]+x[j],y[i]+y[j])]-1; } } printf("%d\n",ans/2); return 0; }
- 1
信息
- ID
- 1556
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 3
- 上传者