The Preliminary Contest for ICPC Asia Xuzhou 2019 徐州网络赛 K题 center

风骨散人Chiam

发布于 2020-10-28 11:11:26

2260

发布于 2020-10-28 11:11:26

文章被收录于专栏：CSDN旧文

You are given a point set with nn 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 (X_c,Y_c)(Xc,Yc)(not necessarily in the point set), so that for every point (X_i,Y_i)(Xi,Yi) in the set, there exists a point (X_j,Y_j)(Xj,Yj) (ii can be equal to jj) in the set satisfying X_c=(X_i+X_j)/2Xc=(Xi+Xj)/2 and Y_c=(Y_i+Y_j)/2Yc=(Yi+Yj)/2.

Input

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

The next nn lines contain nn pair of integers (X_i,Y_i)(Xi,Yi) (-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.

样例输入复制

样例输出复制

样例解释

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

这个题，卡精度，如果除2之后，C++编译器抽风的出来的值不一样，存map就不准了，所以不除2，直接相加储存。

挺简单的。

#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
#define LL long long
#define MAXN 1100
#define  esp 1e-2
map<pair<long long ,long long >,int>m;
int x[MAXN],y[MAXN];
int main()
{
    double a,b;
    int n,i,j,maxx=0;
    scanf("%d",&n);
    if(n==1||n==2) return cout<<0<<endl,0;
    for(i=1; i<=n; i++)
        scanf("%d%d",&x[i],&y[i]);
    for(i=1; i<=n; i++)
        for(j=i+1; j<=n; j++)
        {
            a=x[i]+x[j];
            b=y[i]+y[j];
            m[make_pair(a,b)]++;
            maxx=max(maxx,m[make_pair(a,b)]);
        }
    int cnt=0;
    for(auto po=m.begin(); po!=m.end(); po++)
    {
        if(po->second==maxx)
        {
            int a=po->first.first;
            int b=po->first.second;
            int w=0;
            for(i=1; i<=n; i++)
            {
                if(a==2*x[i]&&b==2*y[i]) w++;
            }
            cnt=max(cnt,w);
        }
    }
    printf("%d",n-2*maxx-cnt);
    return 0;
}

签到题，以为很难，没做。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/09/07 ，如有侵权请联系 cloudcommunity@tencent.com 删除

add