The scoring system for this challenge is binary. Your score is zero unless you pass all tests.

Given $n$ strictly convex simple polygons and $m$ ellipses on a plane, find any point lying in their intersection. Then print two lines of output, where the first line contains the point's ${x}$ coordinate and the second line contains its $y$ coordinate. The point lying on the boundary of an ellipse or polygon is considered to be an inner point. 

Input Format

The first line contains an integer, $n$, denoting the number of polygons. 

The next set of lines defines $n$ polygons, where each polygon ${i}$ is described as follows:

The first line contains an integer, $v_i$, denoting the number of vertices in polygon ${i}$.
Each of the $v_i$ subsequent lines contains two space-separated integers denoting the respective ${x}$ and $y$ coordinates for one of polygon ${i}$'s vertices. The list of vertices is given in counterclockwise order.        

The next line contains an integer, $m$, denoting the number of ellipses. 

Each of the $m$ subsequent lines contains five space-separated integers denoting the respective values of $x_1$, ${y_1}$, $x_2$, $y_2$, and ${a}$, which are the coordinates of the two focal points and the semi-major-axis for an Ellipse.

Constraints

$1\leq n\leq500$
$3\leq v_i\leq1500$
$3\leq\sum\limits_{i=0}^{n-1}v_i\leq1500$
$1\leq m\leq1500$
The coordinates of points are integers in the inclusive range $[-10^4,10^4]$.
All semi-major-axes are integers $\leq10^4$.
It's guaranteed that a solution exists.  
This challenge has binary scoring.  

Output Format

Print two lines describing an $(x,y)$ point inside the intersection. The first line must be a real number denoting the point's ${x}$ coordinate, and the second line must be a real number denoting its $y$ coordinate. Your answer is considered to be correct if there is a point, $(x_0,y_0)$, inside the intersection such that the distance between $(x,y)$ and $(x_0,y_0)$ is at most $\mathbf{10^{-4}}$.

Sample Input
2
4
0 0
2 0
2 1
0 1
3
-1 -1
5 1
0 5
1
1 2 1 4 2

Sample Output
0.999998
1

Explanation

The intersection consists of only one point: $(1,1)$. As its distance to $(0.99998,1)$ is $\leq10^{-4}$, this is a correct answer. Thus, we print the ${x}$ coordinate, ${0.9999}$, on the first line and the $y$ coordinate, ${1}$, on the second line.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Geometry


Solutions:
from math import sqrt

def dist(x1, y1, x2, y2):
	dx = x1 - x2
	dy = y1 - y2
	return sqrt(dx * dx + dy * dy)

def test_edge(x, y, edge):
	dx = edge[2] - edge[0]
	dy = edge[3] - edge[1]
	return dx * y - dy * x >= dx * edge[1] - dy * edge[0]

def ellipse_range(x, y, ellipse):
	d1 = dist(x, y, ellipse[0], ellipse[1])
	d2 = dist(x, y, ellipse[2], ellipse[3])
	return d1 + d2 - ellipse[4] * 2

def solve(edges, ellipses, x1, y1, x2, y2):
	if x2 - x1 < 1e-09:
		return [x1, y1]
	edges2 = []
	for e in edges:
		t1 = test_edge(x1, y1, e)
		t2 = test_edge(x2, y1, e)
		t3 = test_edge(x1, y2, e)
		t4 = test_edge(x2, y2, e)
		if not (t1 or t2 or t3 or t4):
			return None
		if not (t1 and t2 and t3 and t4):
			edges2.append(e)
	ellipses2 = []
	limit = (x2 - x1) * 1.5
	for e in ellipses:
		r1 = ellipse_range(x1, y1, e)
		r2 = ellipse_range(x2, y1, e)
		r3 = ellipse_range(x1, y2, e)
		r4 = ellipse_range(x2, y2, e)
		if not (r1 < limit or r2 < limit or r3 < limit or (r4 < limit)):
			return None
		if not (r1 < 0 and r2 < 0 and (r3 < 0) and (r4 < 0)):
			ellipses2.append(e)
	mx = (x1 + x2) / 2
	my = (y1 + y2) / 2
	ans = solve(edges2, ellipses2, x1, y1, mx, my)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, mx, y1, x2, my)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, x1, my, mx, y2)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, mx, my, x2, y2)
	if ans:
		return ans
	return None
edges = []
for _ in range(int(input())):
	p = []
	numsides = int(input())
	for _ in range(numsides):
		p.append(list(map(int, input().split())))
	for i in range(numsides):
		edges.append(p[i] + p[(i + 1) % numsides])
ellipses = []
for _ in range(int(input())):
	ellipses.append(list(map(int, input().split())))
result = solve(edges, ellipses, -65536, -65536, 65536, 65536)
print(result[0])
print(result[1])


class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def __repr__(self):
		return repr((self.x, self.y))

class Box:

	def __init__(self, minx, maxx, miny, maxy):
		self.minx = minx
		self.maxx = maxx
		self.miny = miny
		self.maxy = maxy

	def __repr__(self):
		return repr((self.minx, self.maxx, self.miny, self.maxy))

	def intersect(self, box):
		self.minx = max(self.minx, box.minx)
		self.maxx = min(self.maxx, box.maxx)
		self.miny = max(self.miny, box.miny)
		self.maxy = min(self.maxy, box.maxy)

	def add(self, point):
		self.minx = min(self.minx, point.x)
		self.maxx = max(self.maxx, point.x)
		self.miny = min(self.miny, point.y)
		self.maxy = max(self.maxy, point.y)

def isOnLeft(a, b, p):
	(dx, dy) = (b.x - a.x, b.y - a.y)
	prod = dy * (p.x - a.x) - dx * (p.y - a.y)
	if prod <= 0:
		return 0
	else:
		return prod * prod / (dx * dx + dy * dy)

class Polygon:

	def __init__(self, v):
		self.v = v
		self.box = None

	def __repr__(self):
		return repr(self.v)

	def isInside(self, point):
		d = max((isOnLeft(self.v[i - 1], self.v[i], point) for i in range(1, len(self.v))))
		d = max(d, isOnLeft(self.v[-1], self.v[0], point))
		return d

	def getBox(self):
		if not self.box:
			self.box = Box(self.v[0].x, self.v[0].x, self.v[0].y, self.v[0].y)
			for point in self.v[1:]:
				self.box.add(point)
		return self.box

class Ellipse:

	def __init__(self, f1, f2, a):
		self.f1 = f1
		self.f2 = f2
		self.a = a
		self.box = None

	def __repr__(self):
		return repr((self.f1, self.f2, self.a))

	def isInside(self, p):
		d = ((p.x - self.f1.x) ** 2 + (p.y - self.f1.y) ** 2) ** 0.5 + ((p.x - self.f2.x) ** 2 + (p.y - self.f2.y) ** 2) ** 0.5 - 2 * self.a
		if d < 0:
			return 0
		else:
			return d * d

	def getBox(self):
		if not self.box:
			self.box = Box(self.f1.x, self.f1.x, self.f1.y, self.f1.y)
			self.box.add(self.f2)
			self.box.minx -= self.a
			self.box.maxx += self.a
			self.box.miny -= self.a
			self.box.maxy += self.a
		return self.box

def getObjects():
	objects = []
	n = int(input())
	for _ in range(n):
		v = int(input())
		vs = []
		for _ in range(v):
			(x, y) = map(int, input().split())
			vs.append(Point(x, y))
		objects.append(Polygon(vs))
	m = int(input())
	for _ in range(m):
		(x1, y1, x2, y2, a) = map(int, input().split())
		objects.append(Ellipse(Point(x1, y1), Point(x2, y2), a))
	return objects

def getDistance(objects, point):
	return sum((o.isInside(point) for o in objects))

def findOneIntersection(objects):
	boundingBox = Box(-10 ** 4, 10 ** 4, -10 ** 4, 10 ** 4)
	for o in objects:
		boundingBox.intersect(o.getBox())
	points = [Point(boundingBox.minx, boundingBox.miny), Point(boundingBox.maxx, boundingBox.miny), Point(boundingBox.maxx, boundingBox.maxy), Point(boundingBox.minx, boundingBox.maxy)]
	objects_ = []
	for o in objects:
		if any((o.isInside(point) > 0 for point in points)):
			objects_.append(o)
	objects = objects_
	objects.append(Polygon(points))
	point = Point((boundingBox.minx + boundingBox.maxx) / 2, (boundingBox.miny + boundingBox.maxy) / 2)
	vector = Point((boundingBox.maxx - boundingBox.minx) / 2, (boundingBox.maxy - boundingBox.miny) / 2)
	scale = 1
	d = getDistance(objects, point)
	while d > 10 ** (-8):
		p1 = Point(point.x + vector.x * scale, point.y + vector.y * scale)
		p2 = Point(point.x + vector.x * scale, point.y - vector.y * scale)
		p3 = Point(point.x - vector.x * scale, point.y - vector.y * scale)
		p4 = Point(point.x - vector.x * scale, point.y + vector.y * scale)
		d1 = getDistance(objects, p1)
		d2 = getDistance(objects, p2)
		d3 = getDistance(objects, p3)
		d4 = getDistance(objects, p4)
		d_ = min(d, d1, d2, d3, d4)
		if d_ == d:
			scale /= 2
		elif d_ == d1:
			point = p1
			d = d1
		elif d_ == d2:
			point = p2
			d = d2
		elif d_ == d3:
			point = p3
			d = d3
		else:
			point = p4
			d = d4
	return point
objects = getObjects()
p = findOneIntersection(objects)
if p:
	print(p.x)
	print(p.y)


from math import sqrt

def dist(x1, y1, x2, y2):
	dx = x1 - x2
	dy = y1 - y2
	return sqrt(dx * dx + dy * dy)

def test_edge(x, y, edge):
	dx = edge[2] - edge[0]
	dy = edge[3] - edge[1]
	return dx * y - dy * x >= dx * edge[1] - dy * edge[0]

def ellipse_range(x, y, ellipse):
	d1 = dist(x, y, ellipse[0], ellipse[1])
	d2 = dist(x, y, ellipse[2], ellipse[3])
	return d1 + d2 - ellipse[4] * 2

def solve(edges, ellipses, x1, y1, x2, y2):
	if x2 - x1 < 1e-09:
		return [x1, y1]
	edges2 = []
	for e in edges:
		t1 = test_edge(x1, y1, e)
		t2 = test_edge(x2, y1, e)
		t3 = test_edge(x1, y2, e)
		t4 = test_edge(x2, y2, e)
		if not (t1 or t2 or t3 or t4):
			return None
		if not (t1 and t2 and t3 and t4):
			edges2.append(e)
	ellipses2 = []
	limit = (x2 - x1) * 1.5
	for e in ellipses:
		r1 = ellipse_range(x1, y1, e)
		r2 = ellipse_range(x2, y1, e)
		r3 = ellipse_range(x1, y2, e)
		r4 = ellipse_range(x2, y2, e)
		if not (r1 < limit or r2 < limit or r3 < limit or (r4 < limit)):
			return None
		if not (r1 < 0 and r2 < 0 and (r3 < 0) and (r4 < 0)):
			ellipses2.append(e)
	mx = (x1 + x2) / 2
	my = (y1 + y2) / 2
	ans = solve(edges2, ellipses2, x1, y1, mx, my)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, mx, y1, x2, my)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, x1, my, mx, y2)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, mx, my, x2, y2)
	if ans:
		return ans
	return None
edges = []
for _ in range(int(input())):
	p = []
	numsides = int(input())
	for _ in range(numsides):
		p.append(list(map(int, input().split())))
	for i in range(numsides):
		edges.append(p[i] + p[(i + 1) % numsides])
ellipses = []
for _ in range(int(input())):
	ellipses.append(list(map(int, input().split())))
result = solve(edges, ellipses, -65536, -65536, 65536, 65536)
print(result[0])
print(result[1])


from math import sqrt

def dist(x1, y1, x2, y2):
	dx = x1 - x2
	dy = y1 - y2
	return sqrt(dx * dx + dy * dy)

def test_edge(x, y, edge):
	dx = edge[2] - edge[0]
	dy = edge[3] - edge[1]
	return dx * y - dy * x >= dx * edge[1] - dy * edge[0]

def ellipse_range(x, y, ellipse):
	d1 = dist(x, y, ellipse[0], ellipse[1])
	d2 = dist(x, y, ellipse[2], ellipse[3])
	return d1 + d2 - ellipse[4] * 2

def solve(edges, ellipses, x1, y1, x2, y2):
	if x2 - x1 < 1e-09:
		return [x1, y1]
	edges2 = []
	for e in edges:
		t1 = test_edge(x1, y1, e)
		t2 = test_edge(x2, y1, e)
		t3 = test_edge(x1, y2, e)
		t4 = test_edge(x2, y2, e)
		if not (t1 or t2 or t3 or t4):
			return None
		if not (t1 and t2 and t3 and t4):
			edges2.append(e)
	ellipses2 = []
	limit = (x2 - x1) * 1.5
	for e in ellipses:
		r1 = ellipse_range(x1, y1, e)
		r2 = ellipse_range(x2, y1, e)
		r3 = ellipse_range(x1, y2, e)
		r4 = ellipse_range(x2, y2, e)
		if not (r1 < limit or r2 < limit or r3 < limit or (r4 < limit)):
			return None
		if not (r1 < 0 and r2 < 0 and (r3 < 0) and (r4 < 0)):
			ellipses2.append(e)
	mx = (x1 + x2) / 2
	my = (y1 + y2) / 2
	ans = solve(edges2, ellipses2, x1, y1, mx, my)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, mx, y1, x2, my)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, x1, my, mx, y2)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, mx, my, x2, y2)
	if ans:
		return ans
	return None
edges = []
for _ in range(int(input())):
	p = []
	numsides = int(input())
	for _ in range(numsides):
		p.append(list(map(int, input().split())))
	for i in range(numsides):
		edges.append(p[i] + p[(i + 1) % numsides])
ellipses = []
for _ in range(int(input())):
	ellipses.append(list(map(int, input().split())))
result = solve(edges, ellipses, -65536, -65536, 65536, 65536)
print(result[0])
print(result[1])


from math import sqrt

def dist(x1, y1, x2, y2):
	dx = x1 - x2
	dy = y1 - y2
	return sqrt(dx * dx + dy * dy)

def test_edge(x, y, edge):
	dx = edge[2] - edge[0]
	dy = edge[3] - edge[1]
	return dx * y - dy * x >= dx * edge[1] - dy * edge[0]

def ellipse_range(x, y, ellipse):
	d1 = dist(x, y, ellipse[0], ellipse[1])
	d2 = dist(x, y, ellipse[2], ellipse[3])
	return d1 + d2 - ellipse[4] * 2

def solve(edges, ellipses, x1, y1, x2, y2):
	if x2 - x1 < 1e-09:
		return [x1, y1]
	edges2 = []
	for e in edges:
		t1 = test_edge(x1, y1, e)
		t2 = test_edge(x2, y1, e)
		t3 = test_edge(x1, y2, e)
		t4 = test_edge(x2, y2, e)
		if not (t1 or t2 or t3 or t4):
			return None
		if not (t1 and t2 and t3 and t4):
			edges2.append(e)
	ellipses2 = []
	limit = (x2 - x1) * 1.5
	for e in ellipses:
		r1 = ellipse_range(x1, y1, e)
		r2 = ellipse_range(x2, y1, e)
		r3 = ellipse_range(x1, y2, e)
		r4 = ellipse_range(x2, y2, e)
		if not (r1 < limit or r2 < limit or r3 < limit or (r4 < limit)):
			return None
		if not (r1 < 0 and r2 < 0 and (r3 < 0) and (r4 < 0)):
			ellipses2.append(e)
	mx = (x1 + x2) / 2
	my = (y1 + y2) / 2
	ans = solve(edges2, ellipses2, x1, y1, mx, my)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, mx, y1, x2, my)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, x1, my, mx, y2)
	if ans:
		return ans
	ans = solve(edges2, ellipses2, mx, my, x2, y2)
	if ans:
		return ans
	return None
edges = []
for _ in range(int(input())):
	p = []
	numsides = int(input())
	for _ in range(numsides):
		p.append(list(map(int, input().split())))
	for i in range(numsides):
		edges.append(p[i] + p[(i + 1) % numsides])
ellipses = []
for _ in range(int(input())):
	ellipses.append(list(map(int, input().split())))
result = solve(edges, ellipses, -65536, -65536, 65536, 65536)
print(result[0])
print(result[1])