[徐州网络赛][平面几何]K- Center

发布于 2019-09-24  885 次阅读


https://nanti.jisuanke.com/t/41393

题意:给你n个点 让你加最少的点 让这个图中心对称 问 最少加几个点

思路:暴力枚举 N*N 寻找两个点的中间点 输入的时候乘2保证中间的点的坐标没有小数 然后用总点数-最多的中间点数即可
PS 这个题没有重点 有重点这样做不对的哦

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=1e6+5;
map<PII,int>MAP;
int x[maxn],y[maxn];
int main()
{
    int n;
    int ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&x[i],&y[i]);
        x[i]*=2;
        y[i]*=2;
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            int a=++MAP[PII((x[i]+x[j])/2,(y[i]+y[j])/2)];
            if(a>ans)ans=a;
        }
    }
    printf("%d\n",n-ans);
    return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。