By

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3170

Solution

根据题意可以分析出两点之间距离为两点x轴坐标差与y轴坐标差的最大值，即切比雪夫距离。注意到 max(a,b)=(a+b)/2+|(a-b)/2| 可推出 max(|a|,|b|)=|(a+b)/2|+|(a-b)/2| 由此可以将原坐标转化，原坐标(x=a,y=b)转为(x=(a+b)/2,y=(a-b)/2) (为了不用double可以不除二，变为最终答案除二)。然后问题变为求曼哈顿距离最短，前缀和随便乱搞一下就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 100100
using namespace std;
inline ll read(){
    char ch; ch=getchar(); ll f=1,x=0;
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
inline void write(ll x){
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10); putchar(x%10+'0');
}
struct data{
    ll x,y,id;
}a[N];
bool cmpx(data x,data y){return x.x<y.x;}
bool cmpy(data x,data y){return x.y<y.y;}
ll n,ans=1e18,sumlx[N],sumrx[N],sumly[N],sumry[N];
int main(){
    n=read();
    for (ll i=1;i<=n;i++){
        ll x=read(),y=read(); 
        a[i].x=x+y;a[i].y=x-y;a[i].id=i;
    }
    sort(a+1,a+1+n,cmpx);
    for (ll i=1;i<=n;i++) 
        sumlx[a[i].id]=sumlx[a[i-1].id]+(a[i].x-a[i-1].x)*(i-1);
    for (ll i=n;i;i--) 
        sumrx[a[i].id]=sumrx[a[i+1].id]+(a[i+1].x-a[i].x)*(n-i);
    sort(a+1,a+1+n,cmpy);
    for (ll i=1;i<=n;i++) 
        sumly[a[i].id]=sumly[a[i-1].id]+(a[i].y-a[i-1].y)*(i-1);
    for (ll i=n;i;i--) 
        sumry[a[i].id]=sumry[a[i+1].id]+(a[i+1].y-a[i].y)*(n-i);
    for (ll i=1;i<=n;i++)
        ans=min(ans,sumlx[i]+sumrx[i]+sumly[i]+sumry[i]);
    write(ans/2);
}

文章目录
  1. 1. Solution