2019徐州网络赛K Center（暴力枚举）

You are given a point set with nnn points on the 2D-plane, your task is to find the smallest number of points you need to add to the point set, so that all the points in the set are center symmetric.

All the points are center symmetric means that you can find a center point (Xc,Yc)(X_c,Y_c)(Xc​,Yc​)(not necessarily in the point set), so that for every point (Xi,Yi)(X_i,Y_i)(Xi​,Yi​) in the set, there exists a point (Xj,Yj)(X_j,Y_j)(Xj​,Yj​) (iii can be equal to jjj) in the set satisfying Xc=(Xi+Xj)/2X_c=(X_i+X_j)/2Xc​=(Xi​+Xj​)/2 and Yc=(Yi+Yj)/2Y_c=(Y_i+Y_j)/2Yc​=(Yi​+Yj​)/2.

Input

The first line contains an integer n(1≤n≤1000)n(1 \le n \le 1000)n(1≤n≤1000).

The next nnn lines contain nnn pair of integers (Xi,Yi)(X_i,Y_i)(Xi​,Yi​) (−106≤Xi,Yi≤106)(-10^6 \le X_i,Y_i \le 10^6)(−106≤Xi​,Yi​≤106) -- the points in the set

Output

Output a single integer -- the minimal number of points you need to add.

样例输入复制

3
2 0
-3 1
0 -2

样例输出复制

1

样例解释

For sample 111, add point (5,−3)(5,-3)(5,−3) into the set, the center point can be (1,−1)(1,-1)(1,−1) .

暴力枚举每个中点，记录每个中点出现次数，取最大值，答案即为n-maxx   因为有n-maxx个点不是以该点为中心，需要添加的点就是这些点关于中心点的对称点

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+30;
struct point
{
    int x,y;
}p[N];
bool cmp(point a,point b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    else
        return a.y<b.y;
}
map<pair<double,double>,int>mp;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        mp.clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
        }
//        sort(p+1,p+n+1,cmp);
        int maxx=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                double xx=1.0*(p[i].x+p[j].x)/2;
                double yy=1.0*(p[i].y+p[j].y)/2;
                pair<double,double>p1;
                p1=make_pair(xx,yy);
                mp[p1]++;
                maxx=max(maxx,mp[p1]);
            }
        }
        cout<<n-maxx<<'\n';
    }
    return 0;
}