| Bytes | Lang | Time | Link |
|---|---|---|---|
| nan | 250621T002153Z | Lucenapo | |
| 074 | Python | 250609T235222Z | Value In |
48 operators
from fractions import Fraction
def C(Ax,Ay,Bx,By,Cx,Cy,Dx,Dy):
Ax,Ay,Bx,By,Cx,Cy,Dx,Dy=map(Fraction,(Ax,Ay,Bx,By,Cx,Cy,Dx,Dy))#convert to Fraction
dBx=Bx-Ax;dBy=Ay-By#4
Bx_=dBx*dBx+dBy*dBy#4
Cx_=(Cx-Ax)*dBx-(Cy-Ay)*dBy#6
Cy_=(Cx-Ax)*dBy+(Cy-Ay)*dBx#6
Dx_=(Dx-Ax)*dBx-(Dy-Ay)*dBy#6
Dy_=(Dx-Ax)*dBy+(Dy-Ay)*dBx#6
if Cy_*Dy_>0:return 0#2
if Cy_==Dy_==0:return(Cx_>=0 or Dx_>=0)and(Cx_<=Bx_ or Dx_<=Bx_)#6
return 0<=(Cx_*Dy_-Dx_*Cy_)/(Dy_-Cy_)<=Bx_#7
42 operators if assigning to already existing variables is allowed
def R(Ax,Ay,Bx,By,Cx,Cy,Dx,Dy):
Ax,Ay,Bx,By,Cx,Cy,Dx,Dy=map(Fraction,(Ax,Ay,Bx,By,Cx,Cy,Dx,Dy))#convert to Fraction
if Ax==Bx:Ax=Ax+Ay;Bx=Bx+By;Cx=Cx+Cy;Dx=Dx+Dy#9
dBx=Bx-Ax;dBy=By-Ay#4
Cx_m=(Cx-Ax)/dBx#3
Cy_=Cy-Ay-Cx_m*dBy#4
Dx_m=(Dx-Ax)/dBx#3
Dy_=Dy-Ay-Dx_m*dBy#4
if Cy_*Dy_>0:return 0#2
if Cy_==Dy_==0:return(Cx_m>=0 or Dx_m>=0)and(Cx_m<=1 or Dx_m<=1)#6
return 0<=(Cx_m*Dy_-Dx_m*Cy_)/(Dy_-Cy_)<=1#7
Uses Fraction only to convert to fraction so that division is exact.
Python, 88 58 74
I originally used bool-int conversions in place of if/else/and/or, and then left it as is once the spec was clarified because l4m2's answer used way fewer operations even if I made the switch so it didn't feel worth it, but apparently it was wrong (at time of writing) so I might as well update mine.
Implements this algorithm with all subroutines inlined and slightly streamlined to improve op count as follows:
If three points are colinear we don't actually need to check if the y-value is in range.nvm- Stolen from l4m2's answer: Instead of evaluating the sign of each orientation and comparing those to each other, multiply them, and if ≤ 0 either the signs are different or they're both 0. For the double 0 case, an inequality check is added to prevent the problem l4m2 had with colinear line segments. If I just compared the signs I'd be doing something like
(1 if o1 > 0 else -1 if o1 < 0 else 0) != (1 if o2 > 0 else -1 if o2 < 0 else 0)which is 5 operations vso1*o2 <= 0 and o1 != o2having 3.
def intersect(x1,y1,x2,y2,x3,y3,x4,y4):
o1 = (y2-y1)*(x3-x2) - (x2-x1)*(y3-y2) # Cost 8
o2 = (y2-y1)*(x4-x2) - (x2-x1)*(y4-y2) # Cost 8
o3 = (y4-y3)*(x1-x4) - (x4-x3)*(y1-y4) # Cost 8
o4 = (y4-y3)*(x2-x4) - (x4-x3)*(y2-y4) # Cost 8
if o1*o2 <= 0 and o1 != o2 and o3*o4 <= 0 and o3 != o4: # Cost 6
return True
elif o1 == 0 and (x1<=x3<=x2 or x1>=x3>=x2) and (y1<=y3<=y2 or y1>=y3>=y2):
return True # Cost 9
elif o2 == 0 and (x1<=x4<=x2 or x1>=x4>=x2) and (y1<=y4<=y2 or y1>=y4>=y2):
return True # Cost 9
elif o3 == 0 and (x3<=x1<=x4 or x3>=x1>=x4) and (y3<=y1<=y4 or y3>=y1>=y4):
return True # Cost 9
else: # Cost 9
return o4 == 0 and (x3<=x2<=x4 or x3>=x2>=x4) and (y3<=y2<=y4 or y3>=y2>=y4)