You are given two squares, one with sides parallel to the coordinate axes, and another one with sides at 45 degrees to the coordinate axes. Find whether the two squares intersect.

The interior of the square is considered to be part of the square, i.e. if one square is completely inside another, they intersect. If the two squares only share one common point, they are also considered to intersect.


-----Input-----

The input data consists of two lines, one for each square, both containing 4 pairs of integers. Each pair represents coordinates of one vertex of the square. Coordinates within each line are either in clockwise or counterclockwise order.

The first line contains the coordinates of the square with sides parallel to the coordinate axes, the second line contains the coordinates of the square at 45 degrees.

All the values are integer and between $-100$ and $100$.


-----Output-----

Print "Yes" if squares intersect, otherwise print "No".

You can print each letter in any case (upper or lower).


-----Examples-----
Input
0 0 6 0 6 6 0 6
1 3 3 5 5 3 3 1

Output
YES

Input
0 0 6 0 6 6 0 6
7 3 9 5 11 3 9 1

Output
NO

Input
6 0 6 6 0 6 0 0
7 4 4 7 7 10 10 7

Output
YES



-----Note-----

In the first example the second square lies entirely within the first square, so they do intersect.

In the second sample squares do not have any points in common.

Here are images corresponding to the samples: [Image]  [Image]  [Image]

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Geometry

Implementation


Solutions:
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a1 = min(a[0::2])
b1 = max(a[0::2])
c1 = min(a[1::2])
d1 = max(a[1::2])
g = sum(b[0::2]) / 4
h = sum(b[1::2]) / 4
r = abs(b[0] - g) + abs(b[1] - h)
for i in range(a1, b1 + 1):
	for j in range(c1, d1 + 1):
		if abs(i - g) + abs(j - h) <= r:
			exit(print('YES'))
print('NO')


a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
x1 = sorted([a[0], a[2], a[4], a[6]])
y1 = sorted([a[1], a[3], a[5], a[7]])
x2 = sorted([b[0], b[2], b[4], b[6]])
y2 = sorted([b[1], b[3], b[5], b[7]])
ans = 'NO'
for i in range(x1[0], x1[3] + 1):
	for j in range(y1[0], y1[3] + 1):
		if x2[0] + y2[1] <= i + j <= x2[3] + y2[1] and y2[0] - x2[1] <= j - i <= y2[3] - x2[1]:
			ans = 'YES'
print(ans)


def main():

	def center(xx):
		return (sum(xx[::2]) * 0.25, sum(xx[1::2]) * 0.25)
	aa = list(map(float, input().split()))
	bb = list(map(float, input().split()))
	(x, y) = center(aa)
	for i in range(0, 8, 2):
		aa[i] -= x
		bb[i] -= x
		aa[i + 1] -= y
		bb[i + 1] -= y
	(x, y) = center(bb)
	if x < 0.0:
		for i in range(0, 8, 2):
			bb[i] *= -1.0
	if y < 0.0:
		for i in range(1, 8, 2):
			bb[i] *= -1.0
	(x, y) = max((aa[i:i + 2] for i in range(0, 8, 2)))
	for i in range(0, 8, 2):
		bb[i] -= x
		bb[i + 1] -= y
	([x1, y1], [x2, y2]) = sorted((bb[i:i + 2] for i in range(0, 8, 2)))[:2]
	print(('NO', 'YES')[x1 <= 0 and x1 + y1 <= 0.0 and (y2 <= 0.0) and (x2 + y2 <= 0.0)])

def __starting_point():
	main()
__starting_point()


def cp(a, b):
	return a[0] * b[1] - a[1] * b[0]

def sub(b, a):
	return (b[0] - a[0], b[1] - a[1])

def ccw(a, b, c):
	r = cp(sub(b, a), sub(c, a))
	if r == 0:
		return 0
	elif r > 0:
		return 1
	else:
		return -1

def sortpts(pts):
	return pts if ccw(pts[0], pts[1], pts[2]) > 0 else list(reversed(pts))

def readpts():
	ip = list(map(int, input().split()))
	return sortpts([(ip[i], ip[i + 1]) for i in range(0, 8, 2)])

def segi(a1, a2, b1, b2):
	c1 = ccw(a1, a2, b1)
	c2 = ccw(a1, a2, b2)
	return c1 != c2

def segib(a1, a2, b1, b2):
	return segi(a1, a2, b1, b2) and segi(b1, b2, a1, a2)

def checkpts(pts1, pts2):
	for p1 in pts1:
		aa = True
		for i in range(4):
			j = (i + 1) % 4
			if ccw(pts2[i], pts2[j], p1) < 0:
				aa = False
		if aa:
			return True
	return False

def checkpts2(pts1, pts2):
	for i in range(4):
		for j in range(4):
			if segib(pts1[i], pts1[(i + 1) % 4], pts2[j], pts2[(j + 1) % 4]):
				return True
	return False
pts1 = readpts()
pts2 = readpts()
print('YES' if checkpts(pts1, pts2) or checkpts(pts2, pts1) or checkpts2(pts1, pts2) else 'NO')


a = list(map(int, input().split()))
b = list(map(int, input().split()))
x1 = min(a[0], a[2], a[4], a[6])
x2 = max(a[0], a[2], a[4], a[6])
y1 = min(a[1], a[3], a[5], a[7])
y2 = max(a[1], a[3], a[5], a[7])
d1 = min(b[0] - b[1], b[2] - b[3], b[4] - b[5], b[6] - b[7])
d2 = max(b[0] - b[1], b[2] - b[3], b[4] - b[5], b[6] - b[7])
s1 = min(b[0] + b[1], b[2] + b[3], b[4] + b[5], b[6] + b[7])
s2 = max(b[0] + b[1], b[2] + b[3], b[4] + b[5], b[6] + b[7])
for x in range(-100, 101):
	for y in range(-100, 101):
		d = x - y
		s = x + y
		if x1 <= x <= x2 and y1 <= y <= y2 and (s1 <= s <= s2) and (d1 <= d <= d2):
			print('YES')
			exit(0)
print('NO')


a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = min(a[0::2])
d = max(a[0::2])
e = min(a[1::2])
f = max(a[1::2])
g = sum(b[0::2]) // 4
h = sum(b[1::2]) // 4
r = abs(b[0] - g) + abs(b[1] - h)
for i in range(c, d + 1):
	for j in range(e, f + 1):
		if abs(i - g) + abs(j - h) <= r:
			print('YES')
			return
print('NO')


import math
eps = 0.001

def dis(p1, p2):
	return math.sqrt((p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]))

def getArea(p1, p2, p3):
	A = p1[0] - p2[0]
	B = p1[1] - p2[1]
	x = (p3[0] * A * A + p3[1] * A * B + p1[0] * B * B - p1[1] * A * B) / (A * A + B * B)
	y = (p1[1] - p2[1]) * (x - p1[0]) / (p1[0] - p2[0]) + p1[1]
	p4 = (x, y)
	return 0.5 * dis(p1, p2) * dis(p3, p4)

def main():
	(x1, y1, x2, y2, x3, y3, x4, y4) = list(map(int, input().split(' ')))
	minX = min(x1, x2, x3, x4)
	maxX = max(x1, x2, x3, x4)
	minY = min(y1, y2, y3, y4)
	maxY = max(y1, y2, y3, y4)
	(x1, y1, x2, y2, x3, y3, x4, y4) = list(map(int, input().split(' ')))
	square_area = dis((x1, y1), (x2, y2)) * dis((x1, y1), (x2, y2))
	for i in range(minX, maxX + 1):
		for j in range(minY, maxY + 1):
			area1 = getArea((x1, y1), (x2, y2), (i, j))
			area2 = getArea((x2, y2), (x3, y3), (i, j))
			area3 = getArea((x3, y3), (x4, y4), (i, j))
			area4 = getArea((x4, y4), (x1, y1), (i, j))
			if area1 + area2 + area3 + area4 - square_area < eps:
				print('YES')
				return
	print('NO')
main()


p1 = input().split()
p1 = [int(x) for x in p1]
p2 = input().split()
p2 = [int(x) for x in p2]
(xmax, xmin, ymax, ymin) = (-1000, 1000, -1000, 1000)
(centrx, centry) = (sum([p2[i] for i in [0, 2, 4, 6]]) / 4, sum([p2[i] for i in [1, 3, 5, 7]]) / 4)
r = abs(centrx - p2[0]) + abs(centry - p2[1])
for i in [0, 2, 4, 6]:
	xmax = max(xmax, p1[i])
	xmin = min(xmin, p1[i])
for i in [1, 3, 5, 7]:
	ymax = max(ymax, p1[i])
	ymin = min(ymin, p1[i])

def Inside(x, y):
	return x <= xmax and x >= xmin and (y <= ymax) and (y >= ymin)
ok = False
for i in range(-100, 101):
	for j in range(-100, 101):
		if abs(i - centrx) + abs(j - centry) <= r:
			ok = ok or Inside(i, j)
print(['NO\n', 'YES\n'][int(ok)])


def check1(point):
	return sq1[0][0] <= point[0] <= sq1[3][0] and sq1[0][1] <= point[1] <= sq1[3][1]

def check2(point):
	return point[0] + sq2[0][1] - sq2[0][0] >= point[1] and point[0] + sq2[3][1] - sq2[3][0] <= point[1] and (-point[0] + sq2[3][1] + sq2[3][0] >= point[1]) and (-point[0] + sq2[0][1] + sq2[0][0] <= point[1])
t = [int(i) for i in input().split()]
sq1 = list(zip(t[::2], t[1::2]))
sq1.sort()
t = [int(i) for i in input().split()]
sq2 = list(zip(t[::2], t[1::2]))
sq2.sort()
(sq2[1], sq2[2]) = (sq2[2], sq2[1])
for i in range(-100, 101):
	for j in range(-100, 101):
		if check1((i, j)) and check2((i, j)):
			print('YES')
			exit()
print('NO')


square1 = list(map(int, input().split(' ')))
square2 = list(map(int, input().split(' ')))
x1 = sorted([square1[2 * i] for i in range(4)])
y1 = sorted([square1[2 * i + 1] for i in range(4)])
x2 = sorted([square2[2 * i] for i in range(4)])
y2 = sorted([square2[2 * i + 1] for i in range(4)])
bool = False
for i in range(x1[0], x1[3] + 1):
	for j in range(y1[0], y1[3] + 1):
		if x2[0] + y2[1] <= i + j <= x2[3] + y2[1] and y2[0] - x2[1] <= j - i <= y2[3] - x2[1]:
			bool = True
if bool:
	print('YES')
else:
	print('NO')


a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = []
y = []
for i in range(8):
	if i % 2 == 0:
		if a[i] not in x:
			x.append(a[i])
	elif a[i] not in y:
		y.append(a[i])
x.sort()
y.sort()
f = 0
nowx = nowfx = b[2]
nowy = nowfy = b[3]
tarx = tarfx = b[4]
tary = tarfy = b[5]
gox = (-b[2] + b[0]) // abs(b[2] - b[0])
goy = (-b[3] + b[1]) // abs(b[3] - b[1])
while nowx != b[0]:
	nowfx += gox
	nowfy += goy
	tarfx += gox
	tarfy += goy
	addx = (tarx - nowx) // abs(tarx - nowx)
	addy = (tary - nowy) // abs(tary - nowy)
	while nowx != tarx and nowy != tary:
		if x[0] <= nowx <= x[1] and y[0] <= nowy <= y[1]:
			f = 1
		nowx += addx
		nowy += addy
	if x[0] <= nowx <= x[1] and y[0] <= nowy <= y[1]:
		f = 1
	nowx += addx
	nowy += addy
	nowx = nowfx
	nowy = nowfy
	tarx = tarfx
	tary = tarfy
addx = (tarx - nowx) // abs(tarx - nowx)
addy = (tary - nowy) // abs(tary - nowy)
while nowx != tarx and nowy != tary:
	if x[0] <= nowx <= x[1] and y[0] <= nowy <= y[1]:
		f = 1
	nowx += addx
	nowy += addy
if x[0] <= nowx <= x[1] and y[0] <= nowy <= y[1]:
	f = 1
nowx += addx
nowy += addy
print('YES' if f else 'NO')


s = list(map(int, input().split()))
s = [s[i:i + 2] for i in range(0, 8, 2)]
s.sort()
t = list(map(int, input().split()))
t = [t[i:i + 2] for i in range(0, 8, 2)]
t.sort()
for i in t:
	if s[0][0] <= i[0] <= s[3][0] and s[0][1] <= i[1] <= s[3][1]:
		print('YES')
		return
for i in s:
	if sum(t[0]) <= sum(i) <= sum(t[3]) and t[0][0] - t[0][1] <= i[0] - i[1] <= t[3][0] - t[3][1]:
		print('YES')
		return
O = [(t[0][0] + t[3][0]) // 2, (t[0][1] + t[3][1]) // 2]
if s[0][0] <= O[0] <= s[3][0] and s[0][1] <= O[1] <= s[3][1]:
	print('YES')
	return
print('NO')


a = list(map(int, input().split()))
b = list(map(int, input().split()))
l1 = min(a[::2])
r1 = max(a[::2])
d1 = min(a[1::2])
u1 = max(a[1::2])
gx = sum(b[::2]) / 4
gy = sum(b[1::2]) / 4
r = abs(gx - b[0]) + abs(gy - b[1])
for i in range(l1, r1 + 1):
	for j in range(d1, u1 + 1):
		if abs(i - gx) + abs(j - gy) <= r:
			print('YES')
			exit()
print('NO')


n = 4
a = list(map(int, input().split()))
am0 = min(a[0], a[2], a[4], a[6])
am1 = max(a[0], a[2], a[4], a[6])
aM0 = min(a[1], a[3], a[5], a[7])
aM1 = max(a[1], a[3], a[5], a[7])
b = list(map(int, input().split()))
bm0 = min(b[0], b[2], b[4], b[6])
bm1 = max(b[0], b[2], b[4], b[6])
bM0 = min(b[1], b[3], b[5], b[7])
bM1 = max(b[1], b[3], b[5], b[7])
for i in range(5):
	if i < 4:
		(x, y) = (b[2 * i], b[2 * i + 1])
	else:
		(x, y) = ((bm0 + bm1) / 2, (bM0 + bM1) / 2)
	if am0 <= x <= am1 and aM0 <= y <= aM1:
		print('YES')
		return
b = [(b[0] - b[1], b[0] + b[1]), (b[2] - b[3], b[2] + b[3]), (b[4] - b[5], b[4] + b[5]), (b[6] - b[7], b[6] + b[7])]
bm0 = min(b[0][0], b[1][0], b[2][0], b[3][0])
bm1 = max(b[0][0], b[1][0], b[2][0], b[3][0])
bM0 = min(b[0][1], b[1][1], b[2][1], b[3][1])
bM1 = max(b[0][1], b[1][1], b[2][1], b[3][1])
for i in range(5):
	if i < 4:
		(x, y) = (a[2 * i], a[2 * i + 1])
	else:
		(x, y) = ((am0 + am1) / 2, (aM0 + aM1) / 2)
	(x, y) = (x - y, x + y)
	if bm0 <= x <= bm1 and bM0 <= y <= bM1:
		print('YES')
		return
print('NO')


def rf():
	cs = list(map(int, input().split(' ')))
	cs = list(zip(cs[0::2], cs[1::2]))
	return cs

def cross(p, p1, p2):
	return (p2[1] - p[1]) * (p1[0] - p[0]) - (p2[0] - p[0]) * (p1[1] - p[1])

def inside(p, f):
	os = 0
	total = 0
	for i in range(len(f)):
		p1 = f[i]
		p2 = f[(i + 1) % len(f)]
		delta = cross(p, p1, p2)
		os += delta
		total += abs(delta)
	os = abs(os)
	return os == total
fs = [rf(), rf()]
res = False
for (f1, f2) in [fs, fs[::-1]]:
	for p in f1:
		if inside(p, f2):
			res = True
	if inside(((f1[0][0] + f1[2][0]) // 2, (f1[0][1] + f1[2][1]) // 2), f2):
		res = True
print(['NO', 'YES'][res])


rd = lambda : list(map(int, input().split()))
z = []
for i in 'ii':
	a = rd()
	z += [a[::2], a[1::2]]
for x in z:
	x.sort()
(u, v, x, y) = z
for i in range(u[0], u[3] + 1):
	for j in range(v[0], v[3] + 1):
		if x[0] + y[1] <= i + j <= x[3] + y[1] and y[0] - x[1] <= j - i <= y[3] - x[1]:
			print('YES')
			exit()
print('NO')


(x1, y1, x2, y2, x3, y3, x4, y4) = map(int, input().split())
(a1, b1, a2, b2, a3, b3, a4, b4) = map(int, input().split())
xy = [(x1, y1), (x2, y2), (x3, y3), (x4, y4)]
ab = [(a1, b1), (a2, b2), (a3, b3), (a4, b4)]
t = 0
for i in range(4):
	if ab[i][0] >= min(x1, x2, x3, x4) and ab[i][0] <= max(x1, x2, x3, x4):
		if ab[i][1] >= min(y1, y2, y3, y4) and ab[i][1] <= max(y1, y2, y3, y4):
			t = 1
ao = (a1 + a2 + a3 + a4 - min(a1, a2, a3, a4) - max(a1, a2, a3, a4)) // 2
bo = (b1 + b2 + b3 + b4 - min(b1, b2, b3, b4) - max(b1, b2, b3, b4)) // 2
if ao >= min(x1, x2, x3, x4) and ao <= max(x1, x2, x3, x4):
	if bo >= min(y1, y2, y3, y4) and bo <= max(y1, y2, y3, y4):
		t = 1
(x1, y1) = (x1 + y1, x1 - y1)
(x2, y2) = (x2 + y2, x2 - y2)
(x3, y3) = (x3 + y3, x3 - y3)
(x4, y4) = (x4 + y4, x4 - y4)
(a1, b1) = (a1 + b1, a1 - b1)
(a2, b2) = (a2 + b2, a2 - b2)
(a3, b3) = (a3 + b3, a3 - b3)
(a4, b4) = (a4 + b4, a4 - b4)
(x1, a1) = (a1, x1)
(x2, a2) = (a2, x2)
(x3, a3) = (a3, x3)
(x4, a4) = (a4, x4)
(y1, b1) = (b1, y1)
(y2, b2) = (b2, y2)
(y3, b3) = (b3, y3)
(y4, b4) = (b4, y4)
xy = [(x1, y1), (x2, y2), (x3, y3), (x4, y4)]
ab = [(a1, b1), (a2, b2), (a3, b3), (a4, b4)]
for i in range(4):
	if ab[i][0] >= min(x1, x2, x3, x4) and ab[i][0] <= max(x1, x2, x3, x4):
		if ab[i][1] >= min(y1, y2, y3, y4) and ab[i][1] <= max(y1, y2, y3, y4):
			t = 1
ao = (a1 + a2 + a3 + a4 - min(a1, a2, a3, a4) - max(a1, a2, a3, a4)) // 2
bo = (b1 + b2 + b3 + b4 - min(b1, b2, b3, b4) - max(b1, b2, b3, b4)) // 2
if ao >= min(x1, x2, x3, x4) and ao <= max(x1, x2, x3, x4):
	if bo >= min(y1, y2, y3, y4) and bo <= max(y1, y2, y3, y4):
		t = 1
if t == 1:
	print('YES')
else:
	print('NO')


import collections
from functools import cmp_to_key
import sys

def getIntList():
	return list(map(int, input().split()))
import bisect
s1 = getIntList()
s2 = getIntList()

def x8(x):
	return x * 8
s1 = map(x8, s1)
s1 = list(s1)
s1 = [(s1[i], s1[i + 1]) for i in range(0, 8, 2)]
s2 = map(x8, s2)
s2 = list(s2)
s2 = [(s2[i], s2[i + 1]) for i in range(0, 8, 2)]
s1x = map(lambda x: x[0], s1)
s1x = list(s1x)
s1xmin = min(s1x)
s1xmax = max(s1x)
s1y = map(lambda x: x[1], s1)
s1y = list(s1y)
s1ymin = min(s1y)
s1ymax = max(s1y)
s2xpy = map(lambda x: x[0] + x[1], s2)
s2xpy = list(s2xpy)
s2xpymin = min(s2xpy)
s2xpymax = max(s2xpy)
s2xsy = map(lambda x: x[0] - x[1], s2)
s2xsy = list(s2xsy)
s2xsymin = min(s2xsy)
s2xsymax = max(s2xsy)
for x in range(-800, 801):
	for y in range(-800, 801):
		if s1xmin <= x <= s1xmax and s1ymin <= y <= s1ymax:
			if s2xpymin <= x + y <= s2xpymax and s2xsymin <= x - y <= s2xsymax:
				print('YES')
				sys.exit()
print('NO')


import sys
input = sys.stdin.readline
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ax1 = min(a[::2])
ax2 = max(a[::2])
ay1 = min(a[1::2])
ay2 = max(a[1::2])
bx1 = min(b[::2])
bx2 = max(b[::2])
by = 0
for i in range(4):
	if b[i * 2] == bx1:
		by = b[i * 2 + 1]
has = 0
for i in range(ax1, ax2 + 1):
	for j in range(ay1, ay2 + 1):
		if i < bx1 or i > bx2:
			continue
		if bx1 <= i <= (bx1 + bx2) // 2 and abs(j - by) <= abs(i - bx1):
			has = 1
		if (bx1 + bx2) // 2 <= i <= bx2 and abs(j - by) <= abs(i - bx2):
			has = 1
print('YES' if has else 'NO')


A = list(map(int, input().split()))
b = list(map(int, input().split()))

def convert(x, y):
	return (y + x, y - x)
AX = []
AY = []
BX = []
BY = []
for i in range(4):
	(x, y) = convert(b[2 * i], b[2 * i + 1])
	if x not in BX:
		BX.append(x)
	if y not in BY:
		BY.append(y)
	if A[2 * i] not in AX:
		AX.append(A[2 * i])
	if A[2 * i + 1] not in AY:
		AY.append(A[2 * i + 1])
AX.sort()
AY.sort()
BX.sort()
BY.sort()
for i in range(-111, 111):
	for j in range(-111, 111):
		(I, J) = convert(i, j)
		if AX[0] <= i <= AX[1] and BX[0] <= I <= BX[1] and (AY[0] <= j <= AY[1]) and (BY[0] <= J <= BY[1]):
			print('YES')
			quit()
print('NO')


a = list(map(int, input().split()))
b = list(map(int, input().split()))
xa = a[0::2]
ya = a[1::2]
xb = b[0::2]
yb = b[1::2]
miny = min(yb)
maxy = max(yb)
for i in range(miny, (miny + maxy) // 2 + 1):
	for j in range(xb[yb.index(miny)] - abs(i - miny), xb[yb.index(miny)] + abs(i - miny) + 1):
		if min(xa) <= j <= max(xa) and min(ya) <= i <= max(ya):
			print('YES')
			return
for i in range(maxy, (miny + maxy) // 2, -1):
	for j in range(xb[yb.index(miny)] - abs(i - maxy), xb[yb.index(miny)] + abs(i - maxy) + 1):
		if min(xa) <= j <= max(xa) and min(ya) <= i <= max(ya):
			print('YES')
			return
print('NO')


import math
sqa = list(map(int, input().split()))
sqb = list(map(int, input().split()))
sq1 = []
sq2 = []

def get_coords(seq, dest):
	(a, b) = (0, 1)
	for i in range(4):
		dest.append((seq[a], seq[b]))
		a += 2
		b += 2

def check_pt(p1, p2, p3):
	if p1[0] - p2[0] == 0 and p3[0] == p1[0] and (abs(p3[1]) <= abs(p1[1] - p2[1])):
		print(1)
		return 1
	elif p1[1] - p2[1] == 0 and p3[1] == p1[1] and (abs(p3[0]) <= abs(p1[0] - p2[0])):
		print(2)
		return 1
	elif p1[0] - p2[0] != 0:
		print(3)
		ab = math.sqrt(math.pow(p3[0] - p1[0], 2) + math.pow(p3[1] - p1[1], 2))
		bc = math.sqrt(math.pow(p3[0] - p2[0], 2) + math.pow(p3[1] - p2[1], 2))
		ac = math.sqrt(math.pow(p2[0] - p1[0], 2) + math.pow(p2[1] - p1[1], 2))
		return ab + bc == ac
	else:
		print(4)
		return 0

def pt_in(r, P):
	areaRectangle = 0.5 * abs((r[0][1] - r[2][1]) * (r[3][0] - r[1][0]) + (r[1][1] - r[3][1]) * (r[0][0] - r[2][0]))
	ABP = 0.5 * (r[0][0] * (P[1] - r[1][1]) + P[0] * (r[1][1] - r[0][1]) + r[1][0] * (r[0][1] - P[1]))
	BCP = 0.5 * (r[2][0] * (P[1] - r[1][1]) + P[0] * (r[1][1] - r[2][1]) + r[1][0] * (r[2][1] - P[1]))
	CDP = 0.5 * (r[2][0] * (P[1] - r[3][1]) + P[0] * (r[3][1] - r[2][1]) + r[3][0] * (r[2][1] - P[1]))
	DAP = 0.5 * (r[0][0] * (P[1] - r[3][1]) + P[0] * (r[3][1] - r[0][1]) + r[3][0] * (r[0][1] - P[1]))
	return areaRectangle == abs(ABP) + abs(BCP) + abs(CDP) + abs(DAP)

def mid_in(r, b):
	x = (b[0][0] + b[2][0]) / 2
	y = (b[1][1] + b[3][1]) / 2
	P = (x, y)
	return pt_in(r, P)
get_coords(sqa, sq1)
get_coords(sqb, sq2)

def check():
	flag = 0
	for j in range(4):
		if pt_in(sq1, sq2[j]) or pt_in(sq2, sq1[j]):
			flag = 1
			break
	if mid_in(sq1, sq2) or mid_in(sq2, sq1):
		flag = 1
	if flag == 1:
		print('YES')
	else:
		print('NO')
check()


class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y
s1 = list()
s2 = list()
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(0, 8, 2):
	s1.append(Point(a[i], a[i + 1]))
for i in range(0, 8, 2):
	s2.append(Point(b[i], b[i + 1]))
intersected = False
x1 = s1[0].x
x2 = s1[1].x != x1 and s1[1].x or s1[2].x
if x1 > x2:
	(x1, x2) = (x2, x1)
y1 = s1[0].y
y2 = s1[1].y != y1 and s1[1].y or s1[2].y
if y1 > y2:
	(y1, y2) = (y2, y1)
for p in s2:
	if x1 <= p.x <= x2 and y1 <= p.y <= y2:
		print('Yes')
		intersected = True
		break
if not intersected:
	m = (s2[0].y - s2[1].y) / (s2[0].x - s2[1].x)
	c1 = s2[0].y - m * s2[0].x
	c2 = s2[0].y + m * s2[0].x
	c3 = s2[2].y - m * s2[2].x
	c4 = s2[2].y + m * s2[2].x
	c = c1
	if c1 > c3:
		(c1, c3) = (c3, c1)
	if c2 > c4:
		(c2, c4) = (c4, c2)
	for p in s1:
		if c1 <= p.y - m * p.x <= c3 and c2 <= p.y + m * p.x <= c4:
			print('Yes')
			intersected = True
			break
	if not intersected:
		if (s2[0].y <= y1 <= s2[1].y or s2[0].y >= y1 >= s2[1].y) and x1 <= (y1 - c) / m <= x2:
			print('Yes')
		elif (s2[0].y <= y2 <= s2[1].y or s2[0].y >= y2 >= s2[1].y) and x1 <= (y2 - c) / m <= x2:
			print('Yes')
		else:
			print('No')


from collections import defaultdict
(x1, y1, x2, y2, x3, y3, x4, y4) = map(int, input().split())
(a1, b1, a2, b2, a3, b3, a4, b4) = map(int, input().split())
first = [(x1, y1), (x2, y2), (x3, y3), (x4, y4)]
sec = [(a1, b1), (a2, b2), (a3, b3), (a4, b4)]
sec.sort()
D = defaultdict(bool)
y = sec[1][1] - 1
for i in range(sec[1][0], sec[0][0] - 1, -1):
	y += 1
	yy = y - 1
	for j in range(i, i + sec[3][0] - sec[1][0] + 1):
		yy += 1
		D[j, yy] = True
first.sort()
ok = False
for i in range(first[0][0], first[2][0] + 1):
	for j in range(first[0][1], first[1][1] + 1):
		if D[i, j]:
			ok = True
			break
	if ok:
		break
if ok:
	print('YES')
else:
	print('NO')


a = list(map(int, input().split()))
(sax, bax, say, bay) = (min(a[0::2]), max(a[0::2]), min(a[1::2]), max(a[1::2]))
b = list(map(int, input().split()))
(sbx, bbx, sby, bby) = (min(b[0::2]), max(b[0::2]), min(b[1::2]), max(b[1::2]))
mp = {}
ans = 'No'
for i in range(sax, bax + 1):
	for j in range(say, bay + 1):
		mp[i, j] = 1
midy = sby + bby >> 1
for i in range(sbx, bbx + 1):
	bnd = min(i - sbx, bbx - i)
	for j in range(midy - bnd, midy + bnd + 1):
		if (i, j) in mp:
			ans = 'Yes'
print(ans)


(x1, y1, x2, y2, x3, y3, x4, y4) = map(int, input().split())
m = list(map(int, input().split()))
a = x1
b = y1
c = x3
d = y3

def ins(x, y):
	global a, b, c, d
	return a <= x <= c and b <= y <= d

class point:

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

def ccw(A, B, C):
	return (C.y - A.y) * (B.x - A.x) > (B.y - A.y) * (C.x - A.x)

def intersect(A, B, C, D):
	return ccw(A, C, D) != ccw(B, C, D) and ccw(A, B, C) != ccw(A, B, D)
for i in range(0, 8, 2):
	(x, y) = m[i:i + 2]
	if ins(x, y):
		print('YES')
		break
else:
	m += m[:2]
	reg = [point(x1, y1), point(x2, y2), point(x3, y3), point(x4, y4)]
	new = [point(m[0], m[1]), point(m[2], m[3]), point(m[4], m[5]), point(m[6], m[7])]
	flag = False
	for p1 in reg:
		for p2 in reg:
			for q1 in new:
				for q2 in new:
					if intersect(p1, p2, q1, q2):
						flag = True
						break
	if flag:
		print('YES')
	else:
		print('NO')


(x1, y1, x2, y2, x3, y3, x4, y4) = [int(s) for s in input().split()]
(x11, y11, x22, y22, x33, y33, x44, y44) = [int(s) for s in input().split()]
min_x1 = min(x1, x2, x3, x4)
min_y1 = min(y1, y2, y3, y4)
max_x1 = max(x1, x2, x3, x4)
max_y1 = max(y1, y2, y3, y4)
min_x11 = min(x11, x22, x33, x44)
min_y11 = min(y11, y22, y33, y44)
max_x11 = max(x11, x22, x33, x44)
max_y11 = max(y11, y22, y33, y44)
a = (max_x11 + min_x11) / 2
b = (max_y11 + min_y11) / 2
d2 = (max_x11 - min_x11) / 2
for x in range(min_x1, max_x1 + 1):
	for y in range(min_y1, max_y1 + 1):
		if abs(x - a) + abs(y - b) <= d2:
			print('yes')
			exit(0)
print('no')


mp = [[0 for i in range(205)] for j in range(205)]
(ax1, ay1, ax2, ay2, ax3, ay3, ax4, ay4) = list(map(int, input().split()))
(bx1, by1, bx2, by2, bx3, by3, bx4, by4) = list(map(int, input().split()))
ax1 += 100
ay1 += 100
ax2 += 100
ay2 += 100
ax3 += 100
ay3 += 100
ax4 += 100
ay4 += 100
bx1 += 100
by1 += 100
bx2 += 100
by2 += 100
bx3 += 100
by3 += 100
bx4 += 100
by4 += 100
x1 = min(ax1, ax2, ax3, ax4)
x2 = max(ax1, ax2, ax3, ax4)
y1 = min(ay1, ay2, ay3, ay4)
y2 = max(ay1, ay2, ay3, ay4)
for i in range(x1, x2 + 1):
	for j in range(y1, y2 + 1):
		mp[i][j] = 1
xx = (bx1 + bx3) // 2
yy = (by1 + by3) // 2
r = abs(min(bx1, bx2, bx3, bx4) - xx)
for i in range(min(bx1, bx2, bx3, bx4), max(bx1, bx2, bx3, bx4) + 1):
	for j in range(min(by1, by2, by3, by4), max(by1, by2, by3, by4) + 1):
		if abs(i - xx) + abs(j - yy) <= r:
			if mp[i][j] == 1:
				print('YES')
				return
print('NO')


I = lambda : list(map(int, input().split()))
(q, w) = (I(), I())

def c(q, w):
	l = 0
	w += [(w[0] + w[4]) / 2, (w[1] + w[5]) / 2]
	for j in range(0, 10, 2):
		(e, r) = (w[j], w[j + 1])
		o = 0
		for i in range(0, 8, 2):
			(a, b) = (q[(i + 4) % 8], q[(i + 5) % 8])
			s = (b - q[i + 1]) * (q[(i + 2) % 8] - q[i]) - (q[(i + 3) % 8] - q[i + 1]) * (a - q[i])
			if s > 0:
				if (r - q[i + 1]) * (q[(i + 2) % 8] - q[i]) - (q[(i + 3) % 8] - q[i + 1]) * (e - q[i]) >= 0:
					o += 1
			elif (r - q[i + 1]) * (q[(i + 2) % 8] - q[i]) - (q[(i + 3) % 8] - q[i + 1]) * (e - q[i]) <= 0:
				o += 1
		if o == 4:
			l = 1
	return l
print('YES' if c(q, w) + c(w, q) else 'NO')


import math as m

class Point:

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

	def __xor__(self, other):
		return float(self.x * other.y - self.y * other.x)

	def __sub__(self, other):
		return Point(self.x - other.x, self.y - other.y)

	def __repr__(self):
		return '%d %d' % (self.x, self.y)

	def mo(self):
		return m.sqrt(self.x * self.x + self.y * self.y)
a = []
b = []
na = list(map(int, input().split(' ')))
nb = list(map(int, input().split(' ')))
for i in range(8):
	if i % 2 == 1:
		a.append(Point(na[i - 1], na[i]))
a.append(Point((a[0].x + a[1].x) / 2, (a[1].y + a[2].y) / 2))
for i in range(8):
	if i % 2 == 1:
		b.append(Point(nb[i - 1], nb[i]))
b.append(Point((b[0].x + b[2].x) / 2, (b[1].y + b[3].y) / 2))

def cmp1(xx, yy):
	if xx.x == yy.x:
		return 1 if xx.y < yy.y else -1
	else:
		return 1 if xx.x > yy.x else -1
s1 = a[1] - a[0]
s2 = a[3] - a[2]
s3 = a[0] - a[3]
s4 = a[1] - a[2]
t1 = b[1] - b[0]
t2 = b[3] - b[2]
t3 = b[0] - b[3]
t4 = b[1] - b[2]

def cal(p, ss1, ss2, ss3, ss4, ll):
	n1 = p - a[0]
	n2 = p - a[2]
	n3 = p - a[3]
	n4 = p - a[2]
	if round(m.fabs(n1 ^ ss1) / ss1.mo() + m.fabs(n2 ^ ss2) / ss2.mo(), 8) == round(ll, 8):
		if round(m.fabs(n3 ^ ss3) / ss3.mo() + m.fabs(n4 ^ ss4) / ss4.mo(), 8) == round(ll, 8):
			return 1
	return 0

def cal2(p, ss1, ss2, ss3, ss4, ll):
	n1 = p - b[0]
	n2 = p - b[2]
	n3 = p - b[3]
	n4 = p - b[2]
	if round(m.fabs(n1 ^ ss1) / ss1.mo() + m.fabs(n2 ^ ss2) / ss2.mo(), 8) == round(ll, 8):
		if round(m.fabs(n3 ^ ss3) / ss3.mo() + m.fabs(n4 ^ ss4) / ss4.mo(), 8) == round(ll, 8):
			return 1
	return 0
flag = 0
for i in range(5):
	if cal(b[i], s1, s2, s3, s4, m.sqrt((a[0].x - a[1].x) ** 2 + (a[0].y - a[1].y) ** 2)) == 1:
		flag = 1
		break
if flag == 0:
	for i in range(5):
		if cal2(a[i], t1, t2, t3, t4, m.sqrt((b[0].x - b[1].x) ** 2 + (b[0].y - b[1].y) ** 2)) == 1:
			flag = 1
			break
if flag == 1:
	print('YES')
else:
	print('NO')


quadrate1 = list(map(int, input().split()))
quadrate2 = list(map(int, input().split()))

def sq2_treug(x1, y1, x2, y2, x3, y3) -> int:
	return (x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1)

def point_in_square(x, y, x1, y1, x2, y2, x3, y3, x4, y4, sq2) -> bool:
	sq1 = abs(sq2_treug(x, y, x1, y1, x2, y2)) + abs(sq2_treug(x, y, x2, y2, x3, y3)) + abs(sq2_treug(x, y, x3, y3, x4, y4)) + abs(sq2_treug(x, y, x4, y4, x1, y1))
	return sq2 == sq1
sq21 = 2 * (max(quadrate1[::2]) - min(quadrate1[::2])) * (max(quadrate1[1::2]) - min(quadrate1[1::2]))
sq22 = (max(quadrate2[::2]) - min(quadrate2[::2])) * (max(quadrate2[1::2]) - min(quadrate2[1::2]))
inter = any([point_in_square(quadrate1[2 * i], quadrate1[2 * i + 1], *quadrate2, sq22) for i in range(4)]) or any([point_in_square(quadrate2[2 * i], quadrate2[2 * i + 1], *quadrate1, sq21) for i in range(4)]) or point_in_square((max(quadrate1[::2]) + min(quadrate1[::2])) // 2, (max(quadrate1[1::2]) + min(quadrate1[1::2])) // 2, *quadrate2, sq22) or point_in_square((max(quadrate2[::2]) + min(quadrate2[::2])) // 2, (max(quadrate2[1::2]) + min(quadrate2[1::2])) // 2, *quadrate1, sq21)
print('YES' if inter else 'NO')