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]

Difficulty: competition

Starter code:

Solutions:
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")
            return
print("NO")


import sys
#sys.stdin=open("data.txt")
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):
        # check this point
        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")


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')


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 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(pts1)
#print(pts2)
print('YES' if checkpts(pts1, pts2) or checkpts(pts2, pts1) or checkpts2(pts1, pts2) else 'NO')


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')
            return
print('NO')


import math
eps = 1e-3

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 .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()


def main():
    def center(xx):
        return sum(xx[::2]) * .25, sum(xx[1::2]) * .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.:
        for i in range(0, 8, 2):
            bb[i] *= -1.
    if y < 0.:
        for i in range(1, 8, 2):
            bb[i] *= -1.
    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. and y2 <= 0. and x2 + y2 <= 0.])


def __starting_point():
    main()

__starting_point()

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(\
        #                 y_A      y_C      x_D      x_B\
                        (r[0][1]-r[2][1])*(r[3][0]-r[1][0])\
        #                  y_B     y_D       x_A     x_C\
                      + (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
    #check point on edge
    for j in range(4):
        '''if check_pt(sq2[0],sq2[1],sq1[j]) or check_pt(sq2[1],sq2[2],sq1[j]) or check_pt(sq2[2],sq2[3],sq1[j]) or check_pt(sq2[0],sq2[3],sq1[j]):
            print(5)
            flag = 1
            break
        if check_pt(sq1[0],sq1[1],sq2[j]) or check_pt(sq1[1],sq1[2],sq2[j]) or check_pt(sq1[2],sq1[3],sq2[j]) or check_pt(sq1[0],sq1[3],sq2[j]):
            print(6)
            flag = 1
            break'''
        #print(j)
        if pt_in(sq1,sq2[j]) or pt_in(sq2,sq1[j]):
            flag = 1
            break
    #check mid in square:
    if mid_in(sq1,sq2) or mid_in(sq2,sq1):
        #print(8)
        flag = 1
    if flag == 1:
        print("YES")
    else:
        print("NO")
check()



#     Codeforces Round #488 by NEAR (Div. 2)
import collections
from functools import cmp_to_key
#key=cmp_to_key(lambda x,y: 1 if x not in y else -1 )

import sys
def getIntList():
    return list(map(int, input().split()))    

import bisect 
            
     
s1 = getIntList()
s2 = getIntList()

def x8(x):
    return x*8
 
s1 = list(map(x8,s1))
s1 = list(s1)
s1 = [ (s1[i],s1[i+1]) for i in range(0,8,2)]
s2 = list(map(x8,s2))
s2 = list(s2)
s2 = [ (s2[i],s2[i+1]) for i in range(0,8,2)]



s1x = [x[0] for x in s1]
s1x = list(s1x)
s1xmin = min(s1x)
s1xmax = max(s1x)
 

s1y = [x[1] for x in s1]
s1y = list(s1y)
s1ymin = min(s1y)
s1ymax = max(s1y)

s2xpy = [x[0] + x[1] for x in s2]
s2xpy = list(s2xpy)
s2xpymin = min(s2xpy)
s2xpymax = max(s2xpy)

s2xsy = [x[0] - x[1] for x in 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')
                return

print('NO')


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)])

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")

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')

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)
s='NO'
for i in range(c,d+1):
	for j in range(e,f+1):
		if abs(i-g)+abs(j-h)<=r:
			s='YES'
print(s)

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')



# Made By Mostafa_Khaled


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

# Cross product of vectors (p1-p) and (p2-p)
def cross(p, p1, p2):
    return (p2[1] - p[1]) * (p1[0] - p[0]) - (p2[0] - p[0]) * (p1[1] - p[1])

# p = (x, y)
# f = [(x1, y1), (x2, y2), ...]
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])


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 :
            print("YES");return
print("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()))
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")


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
        #print(i,j)
#print()
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):
        #print(abs(i-xx),abs(j-yy))
        if abs(i-xx)+abs(j-yy)<=r:
            if mp[i][j]==1:
                #print(i,j)
                print('YES')
                return
print('NO')


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")
            return
print("NO")