自动搬运

查看原文

来自洛谷，原作者为

	浅色调 **

搬运于2025-08-24 21:42:33，当前版本为作者最后更新于2018-04-15 19:57:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

首先，我们知道两点曼哈顿距离公式：

设$S$为题中所求的某个点$(x,y)$到$n$个点的曼哈顿距离之和，即$S=\sum{d}$

那么有$S=\sum{|x-xi|}+\sum{|y-yi|}$

容易发现，$x,y$互不影响求值，于是，我们可以将本题中的横纵坐标分开各自计算。

这样本题就变成了一道中学数学题：求$|x-x1|+|x-x2|+…|x-xn|\;min$，和求$|y-y1|+|y-y2|+…|y-yn|\;min$

由中学的数学知识可知直接求中位数就行了（可以分类讨论，也可以几何意义解决）。

那么，我们直接对$x,y$各自排序：

1、当$n$为奇数时，取$x[n/2+1]$和$y[n/2+1]$，由于题意中不能选给出的点，所以判断：

若该点为给出的点，则枚举它的上下左右四个点上能求得的最小的$S$，更新$ans1$，然后统计$ans$当且仅当这$4$个点的$S=ans1$;

若该点不为给出的点，则直接将$ans1$赋为$S$，$ans2$赋为$1$。

2、当$n$为偶数时，取$x[n/2],x[n/2+1]$和$y[n/2],y[n/2+1]$，显然这$(x[n/2+1]-x[n/2]+1)*(y[n/2+1]-y[n/2]+1)$个点到给定的$n$个点的曼哈顿距离和$S$相等（因为这个矩形中的点的横坐标在$x[n/2],x[n/2+1]$之间，纵坐标也同理），于是枚举矩形中每个点是否是给定的点，求一次$ans1$就$OK$了，先让$ans2$等于这个矩形的点数，每次更新减小就行了。

欢迎来踩博客：five20（本人蒟蒻，写题不易，转载请注明出处）

代码：

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define debug printf("%d %s\n",__LINE__,__FUNCTION__)
using namespace std;
const int N=1e5+7;
int n,b[N],c[N],ans1=233333333,ans2;
struct point{int x,y;}a[N];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
il int gi(){
  int a=0;char x=getchar();bool f=0;
  while((x<'0'||x>'9')&&x!='-')x=getchar();
  if(x=='-')x=getchar(),f=1;
  while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
  return f?-a:a;
}
il int getsum(int x,int y){
  int ans=0;
  for(int i=1;i<=n;i++)ans+=abs(x-b[i])+abs(y-c[i]);
  return ans;
}
int main()
{
  n=gi();
  for(int i=1;i<=n;i++)a[i].x=b[i]=gi(),a[i].y=c[i]=gi();
  sort(b+1,b+n+1);
  sort(c+1,c+n+1);
  if(n&1){
      int x=b[(n>>1)+1],y=c[(n>>1)+1];
      for(int i=0;i<4;i++){
          int xx=x+dx[i],yy=y+dy[i];
          int sum=getsum(xx,yy);
          if(sum<ans1)ans1=sum,ans2=1;
          else if(sum==ans1)++ans2;
      }
  }
  else {
      int x1=b[(n>>1)+1],x2=b[n>>1],y1=c[(n>>1)+1],y2=c[n>>1];
      ans2=(x1-x2+1)*(y1-y2+1);
      ans1=getsum(x1,y1);
      for(int i=1;i<=n;i++)
          if(a[i].x>=x2&&a[i].x<=x1&&a[i].y>=y2&&a[i].y<=y1)ans2--;
  }
  cout<<ans1<<' '<<ans2;
  return 0;
}