#include #include #include #include #include #include using namespace std; #define NMAX 2001 #define eps 1e-10 #define DEBUG_LEVEL 0//1 #define DBG(debug_level, ...) \ { \ if (debug_level <= DEBUG_LEVEL) { \ fprintf(stderr, __VA_ARGS__); \ fflush(stderr); \ } \ } struct Point { int x, y, color; } points[NMAX]; int M, N; double pi; void ReadInput() { scanf("%d %d", &M, &N); assert(1 <= M && M <= 1000); assert(1 <= N && N <= 1000); for (int i = 0; i < M; ++i) { scanf("%d %d", &points[i].x, &points[i].y); assert(-1000000000 <= points[i].x && points[i].x <= 1000000000); assert(-1000000000 <= points[i].y && points[i].y <= 1000000000); points[i].color = 0; } for (int i = M; i < M + N; ++i) { scanf("%d %d", &points[i].x, &points[i].y); assert(-1000000000 <= points[i].x && points[i].x <= 1000000000); assert(-1000000000 <= points[i].y && points[i].y <= 1000000000); points[i].color = 1; } } inline int ComputeMin(int a1, int b1, int a2, int b2) { return min(b1 + a2, a1 + b2); } int cnt[2]; vector> vp; int Solve(int idx) { vp.clear(); for (int i = 0; i < M + N; ++i) { if (i == idx) continue; const int dx = points[i].x - points[idx].x, dy = points[i].y - points[idx].y; assert(dx != 0 || dy != 0); const double u = atan2(dy, dx); vp.push_back({u, i}); vp.push_back({u + 2.0 * pi, i}); } assert(vp.size() == 2 * (M + N - 1)); sort(vp.begin(), vp.end()); int ans = M + N, color_idx = points[idx].color; memset(cnt, 0, sizeof(cnt)); for (int i = 0, j = 0; i < M + N - 1; ++i) { while (j < vp.size() && vp[j].first - vp[i].first <= pi - eps) { ++cnt[points[vp[j].second].color]; ++j; } // idx inside, vp[i].second inside. ++cnt[color_idx]; ans = min(ans, ComputeMin(cnt[0], cnt[1], M - cnt[0], N - cnt[1])); // idx inside, vp[i].second outside. --cnt[points[vp[i].second].color]; ans = min(ans, ComputeMin(cnt[0], cnt[1], M - cnt[0], N - cnt[1])); // idx outside, vp[i].second outside. --cnt[color_idx]; ans = min(ans, ComputeMin(cnt[0], cnt[1], M - cnt[0], N - cnt[1])); // idx outside, vp[i].second inside. ++cnt[points[vp[i].second].color]; ans = min(ans, ComputeMin(cnt[0], cnt[1], M - cnt[0], N - cnt[1])); DBG(1, "idx=%d(%d,%d): i=%d(%d,%d):%.9lf j=%d: cnt0=%d cnt1=%d: ans=%d\n", idx, points[idx].x, points[idx].y, i, points[vp[i].second].x, points[vp[i].second].y, vp[i].first, j, cnt[0], cnt[1], ans); // Move vp[i].second outside. --cnt[points[vp[i].second].color]; } return ans; } int main() { //freopen("x.txt", "r", stdin); //freopen("x.out", "w", stdout); pi = 2.0 * acos(0.0); int T; scanf("%d", &T); assert(1 <= T && T <= 100); while (T--) { ReadInput(); int ans = M + N; for (int idx = 0; idx < M + N; ++idx) ans = min(ans, Solve(idx)); printf("%d\n", ans); } return 0; }