HDU 4312 Meeting point-2（切比雪夫距离转曼哈顿距离）

http://acm.hdu.edu.cn/showproblem.php?pid=4312

题意：在上一题的基础上，由四个方向改为了八个方向。

思路：

引用自http://blog.csdn.net/bigbigship/article/details/43163719。

切比雪夫距离：设a(x1,y1),b(x2,y2);DIS = max(|x1-x2|,|y1-y2|) = (|x1-x2+y1-y2|+|x1-x2-y1+y2|)/2;

我们将点aa的坐标看成（x1+y1,x1-y1）,bb的坐标看成（x2+y2,x2-y2）,从几何意义上讲相当于点在原

坐标系上逆时针旋转45度，并将坐标扩大√2倍。

然后求新的的最小的曼哈顿距离和的一半即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 int n;
 8 
 9 struct node
10 {
11     ll x,y;
12     int id;
13 }p[100005];
14 
15 ll sumx[100005],sumy[100005];
16 ll numx[100005],numy[100005];
17 
18 bool cmp1(node a, node b)
19 {
20     return a.x < b.x;
21 }
22 
23 bool cmp2(node a, node b)
24 {
25     return a.y < b.y;
26 }
27 
28 int main()
29 {
30     //freopen("in.txt","r",stdin);
31     int T;
32     scanf("%d",&T);
33     while(T--)
34     {
35         scanf("%d",&n);
36         for(int i=1;i<=n;i++)
37         {
38             scanf("%lld%lld",&p[i].x,&p[i].y);
39             p[i].id = i;
40             int tmp = p[i].x;
41             p[i].x = tmp - p[i].y;
42             p[i].y = p[i].y + tmp;
43         }
44 
45         sumx[0] = sumy[0] = 0;
46         sort(p+1,p+n+1,cmp1);
47         for(int i=1;i<=n;i++)  sumx[i] = sumx[i-1] + p[i].x;
48         for(int i=1;i<=n;i++)  numx[p[i].id] = ((i-1)*p[i].x-sumx[i-1] + (sumx[n]-sumx[i]) - (n-i)*p[i].x);
49         sort(p+1,p+n+1,cmp2);
50         for(int i=1;i<=n;i++)  sumy[i] = sumy[i-1] + p[i].y;
51         for(int i=1;i<=n;i++)  numy[p[i].id] = ((i-1)*p[i].y-sumy[i-1] + (sumy[n]-sumy[i]) - (n-i)*p[i].y);
52 
53         ll ans = numx[1] + numy[1];
54         for(int i=2;i<=n;i++)
55             ans=min(ans,numx[i]+numy[i]);
56         printf("%lld
",ans/2);
57     }
58     return 0;
59 }