領域を縦と横に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;
- }
