Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You are given N red points and M blue points on a 2D plane.

You are required to delete the minimum number of points(the deleted points can be of both colors) so that it's possible to draw a line such that all remaining red points are on one side of the line while all remaining blue points are on the other side of the line.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains two space-separated integers N and M.

Each of the next N lines contains two integers Xr_{i}, Yr_{i} describing the coordinates of the i-th red point.

Each of the next M lines contains two integers Xb_{i}, Yb_{i} describing the coordinates of the i-th blue point.

------ Output ------ 

For each test case, output a single line containing one integer denoting the minimum number of points to be deleted.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N, M ≤ 1,000$
$1 ≤ sum of N in all test cases ≤ 1,000$
$1 ≤ sum of M in all test cases ≤ 1,000$
$-10^{9} ≤ Xr_{i}, Yr_{i}, Xb_{i}, Yb_{i} ≤ 10^{9}$
$No two points among both red and blue points have same coordinates$
$No three points among both red and blue points are collinear$

------ Subtasks ------ 

Subtask #1 (20 points): 1 ≤ sum of N in all test-cases,  sum of M in all test-cases ≤ 100

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
1
4 4
0 0
10 10
0 10
10 0
12 11
2 1
12 1
2 11
----- Sample Output 1 ------ 
2

Source: codechef | Difficulty: VERY_HARD
Tags: Geometry

Sorting

Amortized analysis

Mathematics


Solutions:
import collections as cs
import math
Point = cs.namedtuple('Point', ['x', 'y', 'col', 'angle'])

def shift_and_set_angles(points, p):
	ans = []
	for q in points:
		x = q.x - p.x
		y = q.y - p.y
		if y >= 0:
			angle = x / math.sqrt(x * x + y * y)
		else:
			angle = -x / math.sqrt(x * x + y * y)
		ans.append(Point(x, y, q.col, angle))
	return ans

def sortbyangle(points, left, right):
	l = left
	r = right
	piv = points[int((left + right) / 2)].angle
	while l <= r:
		while points[l].angle > piv:
			l += 1
		while points[r].angle < piv:
			r -= 1
		if l <= r:
			tmp = points[l]
			points[l] = points[r]
			points[r] = tmp
			l += 1
			r -= 1
	if left < r:
		sortbyangle(points, left, r)
	if right > l:
		sortbyangle(points, l, right)

def printpoints(points):
	for p in points:
		print(p.x, p.y, ' angle: ', p.angle, '; color: ', p.col)

def dotp(p, q):
	return p.x * q.x + p.y * q.y
T = int(input())
for ii in range(T):
	blue = []
	red = []
	(n, m) = [int(i) for i in input().split()]
	for i in range(n):
		(x, y) = [int(j) for j in input().split()]
		blue.append(Point(x, y, 1, -1))
	for i in range(m):
		(x, y) = [int(j) for j in input().split()]
		red.append(Point(x, y, 0, -1))
	ans = 10000000
	for i in range(n):
		points = []
		if i != 0:
			points.extend(blue[:i])
		if i != n - 1:
			points.extend(blue[i + 1:])
		points.extend(red)
		points = shift_and_set_angles(points, blue[i])
		sortbyangle(points, 0, n + m - 2)
		blue_count_pos = 0
		blue_count_neg = 0
		red_count_pos = 0
		red_count_neg = 0
		if points[0].y >= 0:
			normal = Point(points[0].y, -points[0].x, 1, -1)
		else:
			normal = Point(-points[0].y, points[0].x, 1, -1)
		for k in range(1, n + m - 1):
			if dotp(points[k], normal) > 0:
				if points[k].col:
					blue_count_pos += 1
				else:
					red_count_pos += 1
			elif points[k].col:
				blue_count_neg += 1
			else:
				red_count_neg += 1
		if blue_count_pos + red_count_neg < ans:
			ans = blue_count_pos + red_count_neg
		if blue_count_neg + red_count_pos < ans:
			ans = blue_count_neg + red_count_pos
		if points[0].col == 1:
			if points[0].y >= 0:
				blue_count_pos += 1
			else:
				blue_count_neg += 1
		elif points[0].y >= 0:
			red_count_pos += 1
		else:
			red_count_neg += 1
		for k in range(1, n + m - 1):
			if points[k].col == 1:
				if points[k].y < 0:
					blue_count_pos -= 1
				else:
					blue_count_neg -= 1
			elif points[k].y < 0:
				red_count_pos -= 1
			else:
				red_count_neg -= 1
			if blue_count_pos + red_count_neg < ans:
				ans = blue_count_pos + red_count_neg
			if blue_count_neg + red_count_pos < ans:
				ans = blue_count_neg + red_count_pos
			if points[k].col == 1:
				if points[k].y >= 0:
					blue_count_pos += 1
				else:
					blue_count_neg += 1
			elif points[k].y >= 0:
				red_count_pos += 1
			else:
				red_count_neg += 1
	print(ans)