2 条题解

  • 0
    @ 2025-10-8 16:57:47

    四个点关于某点中心对称,显然就形成了一个广义的平行四边形(共线也算)。因此这四个点一定满足 (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
      @ 2025-10-8 16:57:42
      /*
      四个点关于某点中心对称,显然就形成了一个广义的平行四边形(共线也算)。因此这四个点一定满足 
      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

      *【计算几何:四点中心对称】[USACO11MAR] Bovine Bridge Battle S

      信息

      ID
      1556
      时间
      1000ms
      内存
      128MiB
      难度
      10
      标签
      递交数
      3
      已通过
      3
      上传者