n<=10000个点(xi,yi)，找到一个不同于给出的所有点的点，使得该点到所有点的曼哈顿距离最小并找出这样的点的个数。
第一眼看上去这不是中位数嘛，奇数一个点偶数一片，然后找一下这篇区域有几个不符合的点即可。不过要找出“不同于给出的点”的点，那万一中位数那个点被占了，就找它四周四个点即可。
错误！明知道会有中位数那一个点被占了，那怎么就不考虑四周都被占了的情况？
不过可以肯定的是，离中位数越近的点算出来的距离是越小的，尽管与中位数点距离相同的点答案可能不同。因此判断下中位数区域是否大于n，如果是那直接记答案（因为该区域肯定有答案），否则bfs。
为什么判重要用map呢其实用set就好了。。。。
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<algorithm> 5 #include<map> 6 //#include<iostream> 7 using namespace std; 8 9 int n; 10 #define maxn 40011 11 int x[maxn],y[maxn],sx[maxn],sy[maxn]; 12 struct Point 13 { 14 int x,y; 15 bool operator < (const Point &b) const 16 {return x<b.x || (x==b.x && y<b.y);} 17 }p[maxn]; 18 map <Point,bool> mp,vis; 19 int ans,cnt; 20 struct qnode{int d,x,y;}q[maxn];int head,tail; 21 const int dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0},inf=0x3f3f3f3f; 22 int dis(int xx,int yy) 23 { 24 int L=0,R=n+1; 25 while (L<R) 26 { 27 const int mid=(L+R+1)>>1; 28 if (x[mid]<xx) L=mid; 29 else R=mid-1; 30 } 31 int idx=L; 32 L=0;R=n+1; 33 while (L<R) 34 { 35 const int mid=(L+R+1)>>1; 36 if (y[mid]<yy) L=mid; 37 else R=mid-1; 38 } 39 int idy=L; 40 return (2*idx-n)*xx-2*sx[idx]+sx[n]+(2*idy-n)*yy-2*sy[idy]+sy[n]; 41 } 42 bool bfs(int d) 43 { 44 bool flag=0; 45 while (head!=tail && q[head].d==d) 46 { 47 const int nx=q[head].x,ny=q[head++].y; 48 if (head==maxn) head=0; 49 if (!mp.count((Point){nx,ny})) 50 { 51 flag=1;int tmp=dis(nx,ny); 52 if (ans>tmp) 53 { 54 ans=tmp; 55 cnt=1; 56 } 57 else if (ans==tmp) cnt++; 58 } 59 else 60 { 61 for (int i=1;i<=4;i++) 62 { 63 const int px=nx+dx[i],py=ny+dy[i]; 64 if (vis.count((Point){px,py})) continue; 65 vis[(Point){px,py}]=1; 66 qnode &now=q[tail]; 67 now.x=px;now.y=py;now.d=d+1;tail++; 68 } 69 } 70 } 71 return flag; 72 } 73 int main() 74 { 75 scanf("%d",&n); 76 for (int i=1;i<=n;i++) 77 { 78 scanf("%d%d",&x[i],&y[i]); 79 p[i].x=x[i];p[i].y=y[i]; 80 mp[(Point){x[i],y[i]}]=1; 81 } 82 sort(x+1,x+1+n);sort(y+1,y+1+n); 83 sx[0]=0;for (int i=1;i<=n;i++) sx[i]=sx[i-1]+x[i]; 84 sy[0]=0;for (int i=1;i<=n;i++) sy[i]=sy[i-1]+y[i]; 85 int x1=x[(n+1)/2],x2=x[n/2+1],y1=y[(n+1)/2],y2=y[n/2+1]; 86 if (1ll*(x2-x1+1)*(y2-y1+1)>n) 87 { 88 ans=sx[n]-2*sx[(n+1)/2]+sy[n]-2*sy[(n+1)/2];cnt=1ll*(x2-x1+1)*(y2-y1+1); 89 for (int i=1;i<=n;i++) 90 if (p[i].x>=x1 && p[i].x<=x2 && p[i].y>=y1 && p[i].y<=y2) cnt--; 91 printf("%d %d\n",ans,cnt); 92 } 93 else 94 { 95 head=tail=0;ans=inf; 96 for (int i=x1;i<=x2;i++) 97 for (int j=y1;j<=y2;j++) 98 { 99 qnode &now=q[tail]; 100 now.x=i;now.y=j;now.d=0;tail++; 101 vis[(Point){i,j}]=1; 102 } 103 x[0]=y[0]=-inf;x[n+1]=y[n+1]=inf; 104 int play=0; 105 while (!bfs(play++)); 106 printf("%d %d\n",ans,cnt); 107 } 108 return 0; 109 }
