题目链接:https://nanti.jisuanke.com/t/41393
题目大意:
给你n个点,让你添加最少的点使所有的点中心对称。
我们考虑,尽量让现有的点尽可能的配对。无法配对的点。只能额外的添加点。
我们用两重循环,统计任意两个点的中点出现的次数。然后其他点只能添加n-sum个点。sum:所有中点出现的次数最多的次数。
把中点哈希保存。和出现次数一起用map存一下就ok了。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int x[1005], y[1005];
map<LL, int> mp;
int main()
{
int n, smax=0;
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=1; j<=n; j++){
LL X=(1ll*x[i]+x[j])*1e7;
LL Y=(y[i]+y[j]);
mp[X+Y]+=1;
smax=max(mp[X+Y], smax);
}
}
printf("%d\n", n-smax);
return 0;
}