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排序；

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstdlib>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 #define ll long long

 #define N 222222

 ll a[N],b[N];

 using namespace std;

 int main()

 {

     int T;

     scanf("%d",&T);

     while (T--)

     {

         int n,c,d;

         scanf("%d%d%d",&n,&c,&d);

         for (int i=;i<=n;i++)

         {

             int x,y;

             scanf("%d%d",&x,&y);

             a[i]=(ll) c*x+d*y;

             b[i]=(ll) c*x-d*y;

         }

         sort(a+,a+n+);

         sort(b+,b+n+);

         ll ans=;

         ll ans1=;

         for (int i=;i<=n;i++)

         {

             ans1+=a[i];

             ans+=a[i]*i-ans1;

         }

         ans1=;

         for (int i=;i<=n;i++)

         {

             ans1+=b[i];

             ans+=b[i]*i-ans1;

         }

         printf("%lld\n",ans>>);

     }

     return ;

 }

巴特西

codechef Taxi Driver

最新文章

热门文章