题解 P3021 【[USACO11MAR]牛桥战役Bovine Bridge Battle】

feecle6418 · 2019-08-23 10:43:32 · 题解

UPD1:增加了一种解法

UPD2:增加了另一种解法

这么简单的题竟然没有题解？我来发一个吧。

首先，四个点关于某点中心对称，显然就形成了一个广义的平行四边形（共线也算）。因此这四个点一定满足 x_1+x_2=x_3+x_4,y_1+y_2=y_3+y_4。因此我们把所有的 x_1+x_2,y_1+y_2 合成一个 pair，再插入一个map或是哈希表内，即可通过扫描得到答案。注意每一个平行四边形都要被算两次，因此答案要除以二。

代码：

// luogu-judger-enable-o2
#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;
}

扩展：

本校OJ上时间只有500ms，上面方法TLE，如何做？

【优化1】

可以观察到pair是STL，非常慢。我们完全可以用一个数来表示坐标。具体地说，由于坐标值和范围为 [-2e9,2e9]，我们可以用 一种略大于 2e9 的进制 来把两个数压成一个数，比如 2147400000 进制。

【优化2】