def plane(p1,p2,p3):
    v1=VminusV((p2[0],p2[1],heights[p2[0],p2[1]]),(p1[0],p1[1],heights[p1[0],p1[1]]))
    v2=VminusV((p3[0],p3[1],heights[p3[0],p3[1]]),(p1[0],p1[1],heights[p1[0],p1[1]]))
    n=VxV(v1,v2)
    point=(p1[0],p1[1],heights[p1[0],p1[1]])
    d=-(VdotV(n,point))
    return (*n,d)

def getappl(x,y):
    if (int(x)+int(y))%2==0:
        if x%1<y%1:
            pl = plane((int(x),int(y)),(int(x),int(y+1)),(int(x+1),int(y+1)))
        else:
            pl = plane((int(x),int(y)),(int(x+1),int(y+1)),(int(x+1),int(y)))
    else:
        if (1-x%1)<y%1:
            pl = plane((int(x+1),int(y)),(int(x),int(y+1)),(int(x+1),int(y+1)))
        else:
            pl = plane((int(x),int(y)),(int(x),int(y+1)),(int(x+1),int(y)))
    return -(pl[0]*x+pl[1]*y+pl[3])/pl[2]

def hor(p1,p2):
    d = VminusV(p2,p1)
    k=int(max(abs(d[0]),abs(d[1])))
    step = 1/k
    for i in range(k):
        cur = VplusV(p1,VxR(d,i*step))
        if cur[2]<getappl(cur[0],cur[1]):
            return False
    return True