题意：给出n个点的坐标，求一个不与这n个点重合的整数点，使这n个点到这个点的曼哈顿距离和最小，输出最小距离和和满足条件的点的个数
假设我们满足条件的点为（x,y），ans表示最小曼哈顿距离和
易知 ans=sigma(xi-x) + sigma(yi-y) = sigma(xi) + sigma(yi) - n*(x+y) (1<=i<=n)
显然当x为xi序列中位数且y为yi序列中位数时，ans最小
但是题目要求（x,y）不与已知点重合，所以要讨论一下：
（一）n为奇数
①（x,y）不与已知点重合，则直接计算ans，方案数为1
②（x,y）为其中之一的已知点，则最终答案在(x+1,y)、(x-1,y)、(x,y+1)、(x,y-1) 四个点中（即它周围的四个点），每个判断一下并更新ans和方案数即可
（二）n为偶数
最小距离和即为当x和y分别为xi和yi的中位数时计算的ans，
找到从小到大排序后中间的两个数x1、x2、y1、y2，则方案数=（x2-x1+1）*（y2-y1+1）- 横坐标在[x1,x2]且纵坐标在[y1,y2]的已知点个数
注意：判断是否为已知点的时候，不能直接开flag[x,y]，会MLE。
同时在n为偶数的时候，判断范围内的已知点个数不能枚举范围内的点一一判断，而是枚举已知点判断是否在范围内
type rec=record x,y:longint; end; const way:array[1..4,1..2] of longint=((1,0),(-1,0),(0,1),(0,-1)); var n,x1,x2,y1,y2 :longint; ans,xx,yy,tt,tot:longint; tx,ty :longint; i,j,k :longint; x,y :array[0..10010] of longint; a :array[0..10010] of rec; function find(xx,yy:longint):longint; var ans:longint; i:longint; begin ans:=0; for i:=1 to n do inc(ans,abs(x[i]-xx)); for i:=1 to n do inc(ans,abs(y[i]-yy)); exit(ans); end; function check(x,y:longint):boolean ; var i:longint; begin for i:=1 to n do if (x=a[i].x) and (y=a[i].y) then exit(false); exit(true); end; procedure sort1(l,r:longint); var i,j:longint; xx,yy:longint; begin i:=l; j:=r; xx:=x[(l+r)>>1]; while (i<=j) do begin while x[i]<xx do inc(i); while x[j]>xx do dec(j); if (i<=j) then begin yy:=x[i]; x[i]:=x[j]; x[j]:=yy; inc(i); dec(j); end; end; if i<r then sort1(i,r); if j>l then sort1(l,j); end; procedure sort2(l,r:longint); var i,j:longint; xx,yy:longint; begin i:=l; j:=r; yy:=y[(l+r)>>1]; while (i<=j) do begin while y[i]<yy do inc(i); while y[j]>yy do dec(j); if (i<=j) then begin xx:=y[i]; y[i]:=y[j]; y[j]:=xx; inc(i); dec(j); end; end; if i<r then sort2(i,r); if j>l then sort2(l,j); end; begin read(n); for i:=1 to n do begin read(x[i],y[i]); a[i].x:=x[i]; a[i].y:=y[i]; end; sort1(1,n); sort2(1,n); // if (n and 1=1) then begin xx:=x[(n+1)>>1]; yy:=y[(n+1)>>1]; if check(xx,yy) then begin writeln(find(xx,yy),' ',1);exit;; end else begin tot:=0; ans:=maxlongint; for k:=1 to 4 do begin tx:=xx+way[k,1]; ty:=yy+way[k,2]; if (tx>=-10000) and (tx<=10000) and (ty>=-10000) and (ty<=10000) then if check(tx,ty) then begin tt:=find(tx,ty); if tt<ans then begin ans:=tt; tot:=1; end else if tt=ans then inc(tot); end; end; writeln(ans,' ',tot); exit; end; end else begin x1:=x[n>>1]; y1:=y[n>>1]; x2:=x[(n>>1)+1]; y2:=y[(n>>1)+1]; tot:=(x2-x1+1)*(y2-y1+1); ans:=find((x1+x2) div 2,(y1+y2) div 2); for i:=1 to n do if (a[i].x>=x1) and (a[i].x<=x2) and (a[i].y<=y2) and (a[i].y>=y1) then dec(tot); writeln(ans,' ',tot); end; end. ——by Eirlys
