codechef Taxi Driver

题意:

给N个点求任意两个点的“距离”总和：

A,B的“距离”定义为：min(|ax-bx|,|ay-by|） (n<200000)

好题！

解析：

看着没思路

先是公式化简：让 ax=sx+sy;

ay=sx-sy;

bx=tx+ty;

by=tx-ty;

于是：min(|ax-bx|,|ay-by|）=min(ax-bx,bx-ax,ay-by,by-ay)=min(sx-tx+sy-ty,tx-sx+ty-sy,sx-tx+sy-ty,tx-sx+ty-sy);

=|sx-tx|+|sy-ty|

这里就明显了吧：

sx=(ax+ay)/2 sy=(ax-ay)/2

于是分别按sx,sy排序；

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <cstring>
 7 #include <vector>
 8  
 9 #define ll long long
10 #define N 222222
11  
12 ll a[N],b[N];
13 using namespace std;
14  
15 int main()
16 {
17     int T;
18     scanf("%d",&T);
19     while (T--)
20     {
21         int n,c,d;
22         scanf("%d%d%d",&n,&c,&d);
23         for (int i=1;i<=n;i++)
24         {
25             int x,y;
26             scanf("%d%d",&x,&y);
27             a[i]=(ll) c*x+d*y;
28             b[i]=(ll) c*x-d*y;
29         }
30  
31         sort(a+1,a+n+1);
32         sort(b+1,b+n+1);
33  
34         ll ans=0;
35         ll ans1=0;
36         for (int i=1;i<=n;i++)
37         {
38             ans1+=a[i];
39             ans+=a[i]*i-ans1;
40         }
41         ans1=0;
42         for (int i=1;i<=n;i++)
43         {
44             ans1+=b[i];
45             ans+=b[i]*i-ans1;
46         }
47         printf("%lld
",ans>>1);
48     }
49     return 0;
50 }

View Code