Adam and Martha are planning to leave the city after their retirement and build a house in a huge land belonging to their family. To keep everyone happy, they want to build the house at a location having distance _a*d1_ from aunt Kimberly's house, where a is some ratio and d1 is the distance of that location to uncle Bob's house. Also, the house should be at a distance _b*d2_ from uncle Jack's house where b is some ratio and d2 is the distance of the location to aunt Janet's house.

You need to help them find the location of their house.

Input Format 

The first line of input contains two integers a and b (the ratios above). In the next four lines, there are 4 pairs of integers that indicate the coordinates of Kimberly's, Bob's, Jack's, and Janet's houses, respectively.

Output Format 

You must output the coordinate of house with exactly two points after decimal point (rounded to closest one hundredth). If there is no location satisfying the above constraints, output Impossible! If there are more than one possible locations, output a location with minimum  x-coordinate and among the ones having the minimum x-coordinate, a location with minimum y-coordinate. 

Constraints  

1 < a, b <= 1000

-1000 <= all input coordinates <= 1000

Sample Input  

3 4

4 0

0 0

-2 -4

-2 -1

Sample Output  

-2.00 0.00

Explanation 

As required, the point (-2.00, 0.00) has distance 2 from Bob's house and distance 3*2=6 from Kimberly's house. It also has distance 1 from Janet's house and distance 4*1=4 from Jack's house.

Difficulty: MEDIUM_HARD
Tags: Geometry

Starter code:

Solutions:
from fractions import Fraction
from math import sqrt
(a, b) = map(int, input().split())
(xk, yk) = map(int, input().split())
(xb, yb) = map(int, input().split())
(xc, yc) = map(int, input().split())
(xn, yn) = map(int, input().split())
a2 = a * a
x1 = Fraction(xk - a2 * xb, 1 - a2)
y1 = Fraction(yk - a2 * yb, 1 - a2)
r1sq = x1 * x1 + y1 * y1 - Fraction(xk * xk + yk * yk - a2 * (xb * xb + yb * yb), 1 - a2)
b2 = b * b
x2 = Fraction(xc - b2 * xn, 1 - b2)
y2 = Fraction(yc - b2 * yn, 1 - b2)
r2sq = x2 * x2 + y2 * y2 - Fraction(xc * xc + yc * yc - b2 * (xn * xn + yn * yn), 1 - b2)
if x1 == x2 and y1 == y2:
	if r1sq == r2sq:
		x = float(x1) - sqrt(float(r1sq))
		y = float(y1)
		print('{:.2f} {:.2f}'.format(x, y))
	else:
		print('Impossible!')
else:
	dsq = (x1 - x2) ** 2 + (y1 - y2) ** 2
	vsq = r1sq - (r1sq - r2sq + dsq) ** 2 / (4 * dsq)
	if vsq < 0:
		print('Impossible!')
	else:
		v = sqrt(float(vsq / dsq))
		u = float((r1sq - r2sq) / (2 * dsq))
		dx = float(x2 - x1)
		dy = float(y2 - y1)
		(x, y) = min((u * dx - v * dy, u * dy + v * dx), (u * dx + v * dy, u * dy - v * dx))
		x += float(x2 + x1) / 2
		y += float(y2 + y1) / 2
		print('{:.2f} {:.2f}'.format(x, y))


class Cercle:

	def __init__(self, o, r):
		self.o = o
		self.r = r

	def inter(self, other):
		if self.o == other.o:
			if self.r == other.r:
				return (self.o[0] - self.r, self.o[1])
			else:
				return 'Impossible!'
		else:
			d = (self.o[0] - other.o[0]) ** 2 + (self.o[1] - other.o[1]) ** 2
			if d > (self.r + other.r) ** 2:
				return 'Impossible!'
			elif d == (self.r + other.r) ** 2:
				v = ((other.o[0] - self.o[0]) / d ** 0.5, (other.o[1] - self.o[1]) / d ** 0.5)
				return (self.o[0] + self.r * v[0], self.o[1] + self.r * v[1])
			else:
				a = d ** 0.5 / 2 + (self.r ** 2 - other.r ** 2) / (2 * d ** 0.5)
				h = (self.r ** 2 - a * a) ** 0.5
				v = ((other.o[0] - self.o[0]) / d ** 0.5, (other.o[1] - self.o[1]) / d ** 0.5)
				w = (v[1], -v[0])
				return min((self.o[0] + a * v[0] + h * w[0], self.o[1] + a * v[1] + h * w[1]), (self.o[0] + a * v[0] - h * w[0], self.o[1] + a * v[1] - h * w[1]))

def f(x):
	y = str(round(100 * x))
	if len(y) < 3:
		y = '0' * (3 - len(y)) + y
	return y[:-2] + '.' + y[-2:]
(a, b) = map(int, input().split())
(x1, y1) = map(int, input().split())
(x0, y0) = map(int, input().split())
(x3, y3) = map(int, input().split())
(x2, y2) = map(int, input().split())
C = Cercle((x0 - (x1 - x0) / (a * a - 1), y0 - (y1 - y0) / (a * a - 1)), ((x0 - x1) ** 2 + (y0 - y1) ** 2) ** 0.5 * a / (a * a - 1))
CC = Cercle((x2 - (x3 - x2) / (b * b - 1), y2 - (y3 - y2) / (b * b - 1)), ((x2 - x3) ** 2 + (y2 - y3) ** 2) ** 0.5 * b / (b * b - 1))
z = C.inter(CC)
if type(z) == tuple:
	z = f(z[0]) + ' ' + f(z[1])
print(z)


class Cercle:

	def __init__(self, o, r):
		self.o = o
		self.r = r

	def inter(self, other):
		if self.o == other.o:
			if self.r == other.r:
				return (self.o[0] - self.r, self.o[1])
			else:
				return 'Impossible!'
		else:
			d = (self.o[0] - other.o[0]) ** 2 + (self.o[1] - other.o[1]) ** 2
			if d > (self.r + other.r) ** 2:
				return 'Impossible!'
			elif d == (self.r + other.r) ** 2:
				v = ((other.o[0] - self.o[0]) / d ** 0.5, (other.o[1] - self.o[1]) / d ** 0.5)
				return (self.o[0] + self.r * v[0], self.o[1] + self.r * v[1])
			else:
				a = d ** 0.5 / 2 + (self.r ** 2 - other.r ** 2) / (2 * d ** 0.5)
				h = (self.r ** 2 - a * a) ** 0.5
				v = ((other.o[0] - self.o[0]) / d ** 0.5, (other.o[1] - self.o[1]) / d ** 0.5)
				w = (v[1], -v[0])
				return min((self.o[0] + a * v[0] + h * w[0], self.o[1] + a * v[1] + h * w[1]), (self.o[0] + a * v[0] - h * w[0], self.o[1] + a * v[1] - h * w[1]))

def f(x):
	y = str(round(100 * x))
	if len(y) < 3:
		y = '0' * (3 - len(y)) + y
	return y[:-2] + '.' + y[-2:]
(a, b) = map(int, input().split())
(x1, y1) = map(int, input().split())
(x0, y0) = map(int, input().split())
(x3, y3) = map(int, input().split())
(x2, y2) = map(int, input().split())
C = Cercle((x0 - (x1 - x0) / (a * a - 1), y0 - (y1 - y0) / (a * a - 1)), ((x0 - x1) ** 2 + (y0 - y1) ** 2) ** 0.5 * a / (a * a - 1))
CC = Cercle((x2 - (x3 - x2) / (b * b - 1), y2 - (y3 - y2) / (b * b - 1)), ((x2 - x3) ** 2 + (y2 - y3) ** 2) ** 0.5 * b / (b * b - 1))
z = C.inter(CC)
if type(z) == tuple:
	z = f(z[0]) + ' ' + f(z[1])
print(z)


import math

def simplify(v):
	div = v[0]
	for i in v:
		div = math.gcd(i, div)
	return list(map(lambda x: x // div, v))

def dist(x1, y1, x2, y2):
	return math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
[rat1, rat2] = list(map(int, input().split()))
[x1, y1] = list(map(int, input().split()))
[x2, y2] = list(map(int, input().split()))
[x3, y3] = list(map(int, input().split()))
[x4, y4] = list(map(int, input().split()))
if rat1 == 1 and rat2 == 1:
	l12 = [x2 - x1, y2 - y1, x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1]
	l34 = [x4 - x3, y4 - y3, x4 * x4 + y4 * y4 - x3 * x3 - y3 * y3]
	x = (l12[2] * l34[1] - l34[2] * l12[1]) / (l12[0] * l34[1] - l34[0] * l12[1])
	y = -(l12[2] * l34[0] - l34[2] * l12[0]) / (l12[0] * l34[1] - l34[0] * l12[1])
else:
	if rat2 == 1:
		[rat1, rat2] = [rat2, rat1]
		[x1, x2, y1, y2] = [x3, x4, y3, y4]
	poly1 = [rat1 * rat1 - 1, -2 * (rat1 * rat1 * x2 - x1), -2 * (rat1 * rat1 * y2 - y1), rat1 * rat1 * x2 * x2 - x1 * x1 + rat1 * rat1 * y2 * y2 - y1 * y1]
	poly2 = [rat2 * rat2 - 1, -2 * (rat2 * rat2 * x4 - x3), -2 * (rat2 * rat2 * y4 - y3), rat2 * rat2 * x4 * x4 - x3 * x3 + rat2 * rat2 * y4 * y4 - y3 * y3]
	poly1 = simplify(poly1)
	poly2 = simplify(poly2)
	line = list(map(lambda i: poly2[i] * poly1[0] - poly1[i] * poly2[0], range(4)))
	try:
		if line[0] == 0 and line[1] == 0 and (line[2] == 0) and (line[3] == 0):
			y = -poly1[2] / (2 * poly1[0])
			xpoly = [poly1[0], poly1[1], poly1[0] * y * y + poly1[2] * y + poly1[3]]
			x = (-xpoly[1] - math.sqrt(xpoly[1] * xpoly[1] - 4 * xpoly[0] * xpoly[2])) / (2 * xpoly[0])
		else:
			line = simplify(line)
			if line[2] == 0:
				x = -line[3] / line[1]
				ypoly = [poly1[0], poly1[2], poly1[0] * x * x + poly1[1] * x + poly1[3]]
				y = (-ypoly[1] - math.sqrt(ypoly[1] * ypoly[1] - 4 * ypoly[0] * ypoly[2])) / (2 * ypoly[0])
			elif line[1] == 0:
				y = -line[3] / line[2]
				xpoly = [poly1[0], poly1[1], poly1[0] * y * y + poly1[2] * y + poly1[3]]
				x = (-xpoly[1] - math.sqrt(xpoly[1] * xpoly[1] - 4 * xpoly[0] * xpoly[2])) / (2 * xpoly[0])
			else:
				xpoly = [0] * 3
				xpoly[0] = poly1[0] * (line[1] * line[1] + line[2] * line[2])
				xpoly[1] = 2 * poly1[0] * line[1] * line[3] + poly1[1] * line[2] * line[2] - poly1[2] * line[2] * line[1]
				xpoly[2] = poly1[0] * line[3] * line[3] - poly1[2] * line[2] * line[3] + poly1[3] * line[2] * line[2]
				x = (-xpoly[1] - math.sqrt(xpoly[1] * xpoly[1] - 4 * xpoly[0] * xpoly[2])) / (2 * xpoly[0])
				y = -(line[3] + line[1] * x) / line[2]
		print('%.2f %.2f' % (x, y))
	except:
		print('Impossible!')


from fractions import Fraction
from math import sqrt
(a, b) = map(int, input().split())
(xk, yk) = map(int, input().split())
(xb, yb) = map(int, input().split())
(xc, yc) = map(int, input().split())
(xn, yn) = map(int, input().split())
a2 = a * a
x1 = Fraction(xk - a2 * xb, 1 - a2)
y1 = Fraction(yk - a2 * yb, 1 - a2)
r1sq = x1 * x1 + y1 * y1 - Fraction(xk * xk + yk * yk - a2 * (xb * xb + yb * yb), 1 - a2)
b2 = b * b
x2 = Fraction(xc - b2 * xn, 1 - b2)
y2 = Fraction(yc - b2 * yn, 1 - b2)
r2sq = x2 * x2 + y2 * y2 - Fraction(xc * xc + yc * yc - b2 * (xn * xn + yn * yn), 1 - b2)
if x1 == x2 and y1 == y2:
	if r1sq == r2sq:
		x = float(x1) - sqrt(float(r1sq))
		y = float(y1)
		print('{:.2f} {:.2f}'.format(x, y))
	else:
		print('Impossible!')
else:
	dsq = (x1 - x2) ** 2 + (y1 - y2) ** 2
	vsq = r1sq - (r1sq - r2sq + dsq) ** 2 / (4 * dsq)
	if vsq < 0:
		print('Impossible!')
	else:
		v = sqrt(float(vsq / dsq))
		u = float((r1sq - r2sq) / (2 * dsq))
		dx = float(x2 - x1)
		dy = float(y2 - y1)
		(x, y) = min((u * dx - v * dy, u * dy + v * dx), (u * dx + v * dy, u * dy - v * dx))
		x += float(x2 + x1) / 2
		y += float(y2 + y1) / 2
		print('{:.2f} {:.2f}'.format(x, y))


from fractions import Fraction
from math import sqrt
(a, b) = map(int, input().split())
(xk, yk) = map(int, input().split())
(xb, yb) = map(int, input().split())
(xc, yc) = map(int, input().split())
(xn, yn) = map(int, input().split())
a2 = a * a
x1 = Fraction(xk - a2 * xb, 1 - a2)
y1 = Fraction(yk - a2 * yb, 1 - a2)
r1sq = x1 * x1 + y1 * y1 - Fraction(xk * xk + yk * yk - a2 * (xb * xb + yb * yb), 1 - a2)
b2 = b * b
x2 = Fraction(xc - b2 * xn, 1 - b2)
y2 = Fraction(yc - b2 * yn, 1 - b2)
r2sq = x2 * x2 + y2 * y2 - Fraction(xc * xc + yc * yc - b2 * (xn * xn + yn * yn), 1 - b2)
if x1 == x2 and y1 == y2:
	if r1sq == r2sq:
		x = float(x1) - sqrt(float(r1sq))
		y = float(y1)
		print('{:.2f} {:.2f}'.format(x, y))
	else:
		print('Impossible!')
else:
	dsq = (x1 - x2) ** 2 + (y1 - y2) ** 2
	vsq = r1sq - (r1sq - r2sq + dsq) ** 2 / (4 * dsq)
	if vsq < 0:
		print('Impossible!')
	else:
		v = sqrt(float(vsq / dsq))
		u = float((r1sq - r2sq) / (2 * dsq))
		dx = float(x2 - x1)
		dy = float(y2 - y1)
		(x, y) = min((u * dx - v * dy, u * dy + v * dx), (u * dx + v * dy, u * dy - v * dx))
		x += float(x2 + x1) / 2
		y += float(y2 + y1) / 2
		print('{:.2f} {:.2f}'.format(x, y))