The Preliminary Contest for ICPC Asia Xuzhou 2019 徐州网络赛 K题 center
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.
样例输入复制
3
2 0
-3 1
0 -2
样例输出复制
1
样例解释
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;
}
签到题,以为很难,没做。
最新文章
- Linux下按程序查实时流量 network traffic
- C# HttpWebReqeust和HttpWebResponse发送请求
- oracle 监控
- [原创]AM3352 + TPS65910 调试方法+调试记录
- unity中UI界面显示FPS
- Part 72 to 81 Talking about Dictionary and List collection in C#
- npm 国内镜像资源 --转载
- Codeforces 328B-Sheldon and Ice Pieces(馋)
- hdu 1166 线段树(sum+单点修改)
- Linux 下的一个全新的性能测量和调式诊断工具 Systemtap, 第 2 部分: DTrace
- datatables隐藏列与createdRow渲染bootstrapSwitch形成的BUG
- Mac下如何配置环境变量JDK
- [精华][推荐]CAS SSO实现单点登录框架学习源码
- Mac 下搭建环境 homebrew/git/node.js/npm/vsCode...
- Java数据解析---SAX
- 导入Spreadsheet到sharepoint2013报错
- day2_python基础
- easyui form提交和formdata提交记录
- (17)Questioning the universe
- 【C#数据结构系列】排序