首页 技术 正文
技术 2022年11月23日
0 收藏 613 点赞 4,896 浏览 2389 个字

  题目传送门

  

题目描述

After scrimping and saving for years, Farmer John has decided to build a new barn. He wants the barn to be highly accessible, and he knows the coordinates of the grazing spots of all N (2 ≤ N ≤ 10,000 cows. Each grazing spot is at a point with integer coordinates (Xi, Yi) (-10,000 ≤ Xi ≤ 10,000; -10,000 ≤ Yi ≤ 10,000). The hungry cows never graze in spots that are horizontally or vertically adjacent.

The barn must be placed at integer coordinates and cannot be on any cow’s grazing spot. The inconvenience of the barn for any cow is given the Manhattan distance formula | X – Xi | + | Y – Yi|, where (X, Y) and (Xi, Yi) are the coordinates of the barn and the cow’s grazing spot, respectively. Where should the barn be constructed in order to minimize the sum of its inconvenience for all the cows? 给出平面上n个不相邻的点,要求到这n个点的曼哈顿距离之和最小的点的个数ans2,和这个最小距离ans1。

输入输出格式

输入格式:

Line 1: A single integer: N

Lines 2..N+1: Line i+1 contains two space-separated integers which are the grazing location (Xi, Yi) of cow i

输出格式:

Line 1: Two space-separated integers: the minimum inconvenience for the barn and the number of spots on which Farmer John can build the barn to achieve this minimum.

输入输出样例

输入样例#1: 复制

4
1 -3
0 1
-2 1
1 -1

输出样例#1: 复制

10 4

说明

The minimum inconvenience is 10, and there are 4 spots that Farmer John can build the farm to achieve this: (0, -1), (0, 0), (1, 0), and (1, 1).


  分析:由题意可以得出,ans2=∑(|x-x[i]|+|y-y[i]|),那么很显然越是靠中的点ans2就会越小,那么就要分情况来考虑,如果n是奇数,那么就直接由各个点的中位点来算(也就是排序以后得到一个x[n/2+1],y[n/2+1]),但是要求不能有已经给出的点,所以要在(x,y+1),(x+1,y),(x-1,y),(x,y-1)四个点,即上下左右每个点进行计算和判断。如果n是偶数,那么排序以后得到的是一个2*2的矩阵,那么就在这个矩阵中对每个点进行计算判断。具体看代码。

  Code:

//It is made by HolseLee on 21st Apr 2018
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+;
int n,ans,cnt;
int dx[]={,,,-};
int dy[]={,-,,};
struct Node{
int x,y;
}a[N];
bool cmpx(Node a,Node b)
{return a.x<b.x;}
bool cmpy(Node a,Node b)
{return a.y<b.y;}
inline int Abs(int x)
{return x>?x:-x;}
bool judge(int x,int y)
{
for(int i=;i<=n;i++)
if(a[i].x==x&&a[i].y==y)
return false;
else return true;
}
int getans(int x,int y)
{
int ret=;
for(int i=;i<=n;i++)
ret+=(Abs(a[i].x-x)+Abs(a[i].y-y));
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
int x,y;
for(int i=;i<=n;i++)
cin>>a[i].x>>a[i].y;
if(n%==){
sort(a+,a+n+,cmpx);
x=a[n/+].x;
sort(a+,a+n+,cmpy);
y=a[n/+].y;
ans=N<<;cnt=;
for(int i=;i<;i++){
int X=x+dx[i],Y=y+dy[i];
int num=getans(X,Y);
if(num<ans)ans=num,cnt=;
else if(num==ans)cnt++;
}
}
else{
sort(a+,a+n+,cmpx);
int xs=a[n/].x,xe=a[n/+].x;
sort(a+,a+n+,cmpy);
int ys=a[n/].y,ye=a[n/+].y;
cnt=(xe-xs+)*(ye-ys+);
for(int i=;i<=n;i++){
if(a[i].x>=xs&&a[i].y>=ys&&a[i].x<=xe&&a[i].y<=ye)
cnt--;
ans+=(Abs(a[i].x-xs)+Abs(a[i].y-ys));
}
}
cout<<ans<<" "<<cnt<<"\n";
return ;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141746.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站