gym101482G 距离转化 三分 思维

(Updated: )
(5 mins to read)

给定二维平面上n个点的坐标，让你找一个点，最小化所有点到这个点的曼哈顿距离之和，并且要求每个点到该点的曼哈顿距离不能超过d$n \leq 100000,d \leq 2\times 10^9$

做法

如果没有d的限制，答案就是这n个点x坐标的中位数和y坐标的中位数。加上d的限制后，对于每个点都有一个菱形的限制区域，所以最后的可行域就是这n个点限制的菱形区域的并，菱形不好处理，我们转化成切比雪夫距离后就变成了正方形，维护L，R，D，U，那么两个正方形的并就是max(L)，min®，max(D)，min(U)。曼哈顿距离中x、y两维是独立的，而每一维又是一个凹函数，所以在可行域范围内三分套三分即可。给定一个点的坐标，计算n个点到这个点的曼哈顿距离和可以通过二分$O(\log n)$解决。(x,y) -> (x+y,x-y) 原坐标系的曼哈顿距离->新坐标系的切比雪夫距离(x,y) -> ((x+y)/2,(x-y)/2) 原坐标系的切比雪夫距离->新坐标系的曼哈顿距离我们维护的LRDU是在切比雪夫坐标系中，而三分的范围是在曼哈顿坐标中的，所以x的三分范围应该是[(L+D)/2,(R+U)/2]，确定了x后，$L\leqx+y \leq R,D\leq x-y \leq U$，那么y的三分范围就是[max(L-x,x-U),min(R-x,x-D)]了

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const ll LINF = 1e18 + 5;
int n, x[N], y[N], d;
ll U, D, L, R, prex[N], prey[N];
ll f(ll a, ll b)
{
  int p = upper_bound(x+1, x+n+1, a) - x - 1, q = upper_bound(y+1, y+n+1, b) - y - 1;
  return a*p - prex[p] + b*q - prey[q] - (n-p)*a + (prex[n] - prex[p]) - (n-q)*b + (prey[n] - prey[q]);
}
ll cal(ll x)
{
  ll l = max(x-U, L-x), r = min(x-D, R-x), ans = LINF;
  while(l<=r)
  {
    ll mid = (2*l+r)/3, mmid = (2*r+l+2)/3;
    ll fmid = f(x, mid), fmmid = f(x, mmid);
    if(fmid<=fmmid)
    {
      ans = min(ans, fmid);
      r = mmid - 1;
    }
    else
    {
      ans = min(ans, fmmid);
      l = mid + 1;
    }
  }
  return ans;
}
int main()
{
  while(~scanf("%d", &n))
  {
    for(int i=1; i<=n; i++) scanf("%d%d", x+i, y+i);
    scanf("%d", &d);
    U = LINF, D = -LINF, L = -LINF, R = LINF;
    for(int i=1; i<=n; i++)
    {
      ll cx = x[i] + y[i], cy = x[i] - y[i];
      U = min(U, cy+d);
      D = max(D, cy-d);
      L = max(L, cx-d);
      R = min(R, cx+d);
    }
    if(D>U||L>R)
    {
      puts("impossible");
      continue;
    }
    sort(x+1, x+n+1); sort(y+1, y+n+1);
    for(int i=1; i<=n; i++) prex[i] = prex[i-1] + x[i], prey[i] = prey[i-1] + y[i];
    ll l = (L+D)/2, r = (R+U)/2, ans = LINF;
    while(l<=r)
    {
      ll mid = (2*l+r)/3, mmid = (2*r+l+2)/3;
      ll fmid = cal(mid), fmmid = cal(mmid);
      if(fmid<=fmmid)
      {
        ans = min(ans, fmid);
        r = mmid - 1;
      }
      else
      {
        ans = min(ans, fmmid);
        l = mid + 1;
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}