There are N points on X-Y plane with integer coordinates (xi, yi). You are given a set of polygons with all of its edges parallel to the axes (in other words, all angles of the polygons are 90 degree angles and all lines are in the cardinal directions. There are no diagonals). For each polygon your program should find the number of points lying inside it. A point located on the border of polygon is also considered to be inside the polygon.

Input Format 

The first line contains two integers N and Q. The next line contains N space-separated integer coordinates (xi,yi). Q queries follow. Each query consists of a single integer Mi in the first line, followed by Mi space separated integer coordinates (x[i][j],y[i][j]) specifying the boundary of the query polygon in clock-wise order.

Polygon is an alternating sequence of vertical line segments and horizontal line segments.
Polygon has Mi edges, where (x[i][j],y[i][j]) is connected to (x[i][(j+1)%Mi], y[i][(j+1)%Mi].
For each 0 <= j < Mi, either x[i][(j+1)%Mi] == x[i][j] or y[i][(j+1)%Mi] == y[i][j] but not both.
It is guaranteed that the polygon is not self-intersecting.

Output Format 

For each query output the number of points inside the query polygon in a separate line.

Constraints 

1 <= N <= 20,000 

1 <= Q <= 20,000 

4 <= Mi <= 20 

-200,000 <= x[i][j],y[i][j] <= 200,000

Sample Input #1 

16 2 

0 0 

0 1 

0 2 

0 3 

1 0 

1 1 

1 2 

1 3 

2 0 

2 1 

2 2 

2 3 

3 0 

3 1 

3 2 

3 3 

8 

0 0 

0 1 

1 1 

1 2 

0 2 

0 3 

3 3 

3 0 

4 

0 0 

0 1 

1 1 

1 0

Sample Output #1: 

16 

4

Sample Input #2: 

6 1 

1 1 

3 3 

3 5 

5 2 

6 3 

7 4 

10 

1 3 

1 6 

4 6 

4 3 

6 3 

6 1 

4 1 

4 2 

3 2 

3 3

Sample Output #2: 

4

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Geometry


Solutions:
class QuadTree:

	def __init__(self, pts):
		self.num = len(pts)
		yvals = sorted((pt[1] for pt in pts))
		self.box = (pts[0][0], yvals[0], pts[-1][0], yvals[-1])
		self.subtrees = []
		self.pts = []
		if self.box[0] < self.box[2] or self.box[1] < self.box[3]:
			i = (len(pts) - 1) // 2
			x = pts[i][0]
			y = yvals[i]
			parts = [[], [], [], []]
			for pt in pts:
				i = 1 if pt[0] > x else 0
				if pt[1] > y:
					i += 2
				parts[i].append(pt)
			for subpts in parts:
				if len(subpts) > 8:
					self.subtrees.append(QuadTree(subpts))
				else:
					self.pts.extend(subpts)

	def count(self, boxes):
		for box in boxes:
			if self.box[0] >= box[0] and self.box[1] >= box[1] and (self.box[2] <= box[2]) and (self.box[3] <= box[3]):
				return self.num
		keep = []
		for box in boxes:
			if self.box[0] <= box[2] and self.box[1] <= box[3] and (self.box[2] >= box[0]) and (self.box[3] >= box[1]):
				keep.append(box)
		n = 0
		if keep:
			for (x, y) in self.pts:
				for box in keep:
					if x >= box[0] and y >= box[1] and (x <= box[2]) and (y <= box[3]):
						n += 1
						break
			for subtree in self.subtrees:
				n += subtree.count(keep)
		return n

def toBoxes(pts):
	edges = []
	q = pts[-1]
	for p in pts:
		if p[1] == q[1]:
			if p[0] < q[0]:
				edges.append((p[0], q[0], p[1]))
			else:
				edges.append((q[0], p[0], p[1]))
		q = p
	edges.sort()
	i = 0
	boxes = []
	active = []
	left = edges[i][0]
	while i < len(edges) and edges[i][0] <= left:
		active.append(edges[i])
		i += 1
	while active:
		right = min((edge[1] for edge in active))
		if i < len(edges) and edges[i][0] < right:
			right = edges[i][0]
		active.sort(key=lambda edge: edge[2])
		for j in range(0, len(active), 2):
			boxes.append((left, active[j][2], right, active[j + 1][2]))
		active = [edge for edge in active if edge[1] > right]
		while i < len(edges) and edges[i][0] <= right:
			active.append(edges[i])
			i += 1
		left = right
	return boxes

def readPts(N):
	pts = []
	for i in range(N):
		(x, y) = map(int, input().split())
		pts.append((x, y))
	return pts
(N, Q) = map(int, input().split())
pts = readPts(N)
pts.sort()
tree = QuadTree(pts)
for q in range(Q):
	M = int(input())
	pts = readPts(M)
	boxes = toBoxes(pts)
	print(tree.count(boxes))


class QuadTree:

	def __init__(self, pts):
		self.num = len(pts)
		yvals = sorted((pt[1] for pt in pts))
		self.box = (pts[0][0], yvals[0], pts[-1][0], yvals[-1])
		self.subtrees = []
		self.pts = []
		if self.box[0] < self.box[2] or self.box[1] < self.box[3]:
			i = (len(pts) - 1) // 2
			x = pts[i][0]
			y = yvals[i]
			parts = [[], [], [], []]
			for pt in pts:
				i = 1 if pt[0] > x else 0
				if pt[1] > y:
					i += 2
				parts[i].append(pt)
			for subpts in parts:
				if len(subpts) > 8:
					self.subtrees.append(QuadTree(subpts))
				else:
					self.pts.extend(subpts)

	def count(self, boxes):
		for box in boxes:
			if self.box[0] >= box[0] and self.box[1] >= box[1] and (self.box[2] <= box[2]) and (self.box[3] <= box[3]):
				return self.num
		keep = []
		for box in boxes:
			if self.box[0] <= box[2] and self.box[1] <= box[3] and (self.box[2] >= box[0]) and (self.box[3] >= box[1]):
				keep.append(box)
		n = 0
		if keep:
			for (x, y) in self.pts:
				for box in keep:
					if x >= box[0] and y >= box[1] and (x <= box[2]) and (y <= box[3]):
						n += 1
						break
			for subtree in self.subtrees:
				n += subtree.count(keep)
		return n

def toBoxes(pts):
	edges = []
	q = pts[-1]
	for p in pts:
		if p[1] == q[1]:
			if p[0] < q[0]:
				edges.append((p[0], q[0], p[1]))
			else:
				edges.append((q[0], p[0], p[1]))
		q = p
	edges.sort()
	i = 0
	boxes = []
	active = []
	left = edges[i][0]
	while i < len(edges) and edges[i][0] <= left:
		active.append(edges[i])
		i += 1
	while active:
		right = min((edge[1] for edge in active))
		if i < len(edges) and edges[i][0] < right:
			right = edges[i][0]
		active.sort(key=lambda edge: edge[2])
		for j in range(0, len(active), 2):
			boxes.append((left, active[j][2], right, active[j + 1][2]))
		active = [edge for edge in active if edge[1] > right]
		while i < len(edges) and edges[i][0] <= right:
			active.append(edges[i])
			i += 1
		left = right
	return boxes

def readPts(N):
	pts = []
	for i in range(N):
		(x, y) = map(int, input().split())
		pts.append((x, y))
	return pts
(N, Q) = map(int, input().split())
pts = readPts(N)
pts.sort()
tree = QuadTree(pts)
for q in range(Q):
	M = int(input())
	pts = readPts(M)
	boxes = toBoxes(pts)
	print(tree.count(boxes))


class QuadTree:

	def __init__(self, pts):
		self.num = len(pts)
		yvals = sorted((pt[1] for pt in pts))
		self.box = (pts[0][0], yvals[0], pts[-1][0], yvals[-1])
		self.subtrees = []
		self.pts = []
		if self.box[0] < self.box[2] or self.box[1] < self.box[3]:
			i = (len(pts) - 1) // 2
			x = pts[i][0]
			y = yvals[i]
			parts = [[], [], [], []]
			for pt in pts:
				i = 1 if pt[0] > x else 0
				if pt[1] > y:
					i += 2
				parts[i].append(pt)
			for subpts in parts:
				if len(subpts) > 8:
					self.subtrees.append(QuadTree(subpts))
				else:
					self.pts.extend(subpts)

	def count(self, boxes):
		for box in boxes:
			if self.box[0] >= box[0] and self.box[1] >= box[1] and (self.box[2] <= box[2]) and (self.box[3] <= box[3]):
				return self.num
		keep = []
		for box in boxes:
			if self.box[0] <= box[2] and self.box[1] <= box[3] and (self.box[2] >= box[0]) and (self.box[3] >= box[1]):
				keep.append(box)
		n = 0
		if keep:
			for (x, y) in self.pts:
				for box in keep:
					if x >= box[0] and y >= box[1] and (x <= box[2]) and (y <= box[3]):
						n += 1
						break
			for subtree in self.subtrees:
				n += subtree.count(keep)
		return n

def toBoxes(pts):
	edges = []
	q = pts[-1]
	for p in pts:
		if p[1] == q[1]:
			if p[0] < q[0]:
				edges.append((p[0], q[0], p[1]))
			else:
				edges.append((q[0], p[0], p[1]))
		q = p
	edges.sort()
	i = 0
	boxes = []
	active = []
	left = edges[i][0]
	while i < len(edges) and edges[i][0] <= left:
		active.append(edges[i])
		i += 1
	while active:
		right = min((edge[1] for edge in active))
		if i < len(edges) and edges[i][0] < right:
			right = edges[i][0]
		active.sort(key=lambda edge: edge[2])
		for j in range(0, len(active), 2):
			boxes.append((left, active[j][2], right, active[j + 1][2]))
		active = [edge for edge in active if edge[1] > right]
		while i < len(edges) and edges[i][0] <= right:
			active.append(edges[i])
			i += 1
		left = right
	return boxes

def readPts(N):
	pts = []
	for i in range(N):
		(x, y) = map(int, input().split())
		pts.append((x, y))
	return pts
(N, Q) = map(int, input().split())
pts = readPts(N)
pts.sort()
tree = QuadTree(pts)
for q in range(Q):
	M = int(input())
	pts = readPts(M)
	boxes = toBoxes(pts)
	print(tree.count(boxes))