自动搬运

查看原文

来自洛谷，原作者为

	feecle6418 **

搬运于2025-08-24 21:44:28，当前版本为作者最后更新于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】

$map$ 的时间复杂度是一个 $\log$ 的，总时间复杂度为 $O(n^2\log n)$（因为 $O(\log n^2)=O(2\log n)=O(\log n)$。）我们完全可以省掉这个 $\log$：只需把 $map$ 换为哈希表即可。为了省事，你可以直接用STL，比如 $\mathrm{unordered\_map,gp\_hash\_table,cc\_hash\_table}$ 等（第一个需要选C++11，后面两个是 $pb\_ds$，需要引用相应头文件），把时间复杂度优化到 $O(n^2)$。

【优化3】

手写 Hash 表。直接卡到最优解qwq

【时间对比】

• 优化前： 用时2.42s
• 优化后（STL的Hash）： 用时445ms
• 优化后（手写Hash）： 用时272ms

可以看到，优化的效果非常明显。为了防止抄袭，这里就不放最优解的代码了 （实际上是不想被挤下去qwq）

非最优代码（使用gp_hash_table）：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
using namespace std;
int n,ans,x[1005],y[1005];
gp_hash_table<long long,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[((long long)x[i]+x[j])*2147400000ll+(y[i]+y[j])]++;
		}
	}
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			ans+=p[((long long)x[i]+x[j])*2147400000ll+(y[i]+y[j])]-1;
		}
	}
	printf("%d\n",ans/2);
	return 0;
}