LiveArchive5848

分割統治。

領域を縦と横に2分割して、4つの領域に分ける。
縦は2種類の点を分ける様なX軸に垂直な直線で分割し、横はそれっぽい直線で分割する。

横方向に隣合う領域同士の近い点か、斜めの領域同士の点から最近点を探す。
互いに斜めな領域同士の点の移動は、分割に使った縦と横の線の交点を通る様な移動を考える。

あとは、点の数が少なくなるまで横の分割を繰り返す。

#include <algorithm>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

namespace std {
  inline
  bool operator < (const point& a, const point& b)
  {
    return a.imag () < b.imag();
  }
};

const int N = 100000 + 1;
point A[N], B[N];

const int inf = 1 << 28;

inline
int m_dist(const point& a, const point& b)
{
  return abs(a.real() - b.real()) + abs(a.imag() - b.imag());
}

int conque(int begin_a, int end_a, int begin_b, int end_b, point P, int z)
{
  int v = inf;
  int u = inf;
  for (int i = begin_a; i < end_a; ++i) {
    v = min(v, m_dist(A[i], P));
  }
  for (int i = begin_b; i < end_b; ++i) {
    u = min(u, m_dist(B[i], P));
  }
  return v + u;
}

int X;
// [begin_x, end_x)
int divide(int begin_a, int end_a, int begin_b, int end_b)
{
  if (end_a - begin_a < 5 || end_b - begin_b < 5) {
    int ret = inf;
    for (int i = begin_a; i < end_a; ++i) {
      for (int j = begin_b; j < end_b; ++j) {
        ret = min(ret, m_dist(A[i], B[j]));
      }
    }
    return ret;
  }

  int min_I = min(A[begin_a].imag(), B[begin_b].imag());
  int max_I = min(A[end_a - 1].imag(), B[end_b - 1].imag());

  int Y = (double)rand() * (double)(max_I - min_I) / (double)(RAND_MAX) + min_I;
  point P(X, Y);

  int mid_a = lower_bound(A + begin_a, A + end_a, P) - A;
  int mid_b = lower_bound(B + begin_b, B + end_b, P) - B;

  int x = divide(begin_a, mid_a, begin_b, mid_b);
  int y = divide(mid_a, end_a, mid_b, end_b);
  int z = min(x, y);
  z = min(z, conque(begin_a, mid_a, mid_b, end_b, P, z));
  z = min(z, conque(mid_a, end_a, begin_b, mid_b, P, z));
  return z;
}

int main(int argc, char *argv[])
{
  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
      cin >> A[i].real() >> A[i].imag();
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
      cin >> B[i].real() >> B[i].imag();
    }
    int mx = -1;
    for (int i = 0; i < n; ++i) {
      mx = max(mx, (int)A[i].real());
    }
    int mn = inf;
    for (int i = 0; i < m; ++i) {
      mn = min(mn, (int)B[i].real());
    }
    X = abs(mx - mn) / 2;
    sort(A, A + n);
    sort(B, B + m);
    cout << divide(0, n, 0, m) << endl;
  }
  return 0;
}