1 条题解

  • 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;
    }
    
    • 1

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

    信息

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