Check (AB,CD)==0 (orthogonality).
Check (AB, CD, DA) ==0 (planarity).
Check AD>AC>AB,  AC>BC,  BD>BC (order).
Check whether the projections to XY,  YZ,  XZ craddle each other continuations.
It is sufficient to check only the projections to XY plane to get Accepted verdict.

Sounds too complex.
If we replace C, D with their orthogonal projection on AB, then all steps except first collapse to only one step (check D = C*a, a > 1).

Still too complex, though. Over 20 lines in Python. There should be more simple solution...

Edited by author 26.12.2017 04:30

No lengths or projections XY, etc. Using scalar product (sp) and triple product (tp) it is at most five conditions:

  sp(ab,cd) == 0 and tp(ab,bc,cd) == 0 and # ⟂ and planar
  sp(ab,bc) >= 0 and # C after B
  sp(cd,bc) >= 0 and # BC goes in direction of CD
  sp(cd,bd) >= sp(cd,bc) # D after C

And you probably made a mistake. Your 3rd step would make a mistake if intercection is incide AB, incide CD. I am now stuck with 19test and I used some real bulletproof solution, without using float at all.
----------
I do 3rd step buy solving 3x3 matrix and finding t and z, just instead of dividing i only check +or-
    for i in range(3):
        if mtrx[i][1]!=0:
            if ( mtrx[i][0]>=0 and mtrx[i][1]>0 )or( mtrx[i][0]<=0 and mtrx[i][1]<0 ):
                t=True
            else:
                t=False
    for i in range(3):
        if mtrx[i][2]!=0:
            if ( mtrx[i][0]>=0 and mtrx[i][2]>0 )or( mtrx[i][0]<=0 and mtrx[i][2]<0 ):
                z=True
            else:
                z=False
    return t and z
------------
I start to believe, that it is incorrect test result not my soultion

Edited by author 13.04.2026 01:15

Edited by author 13.04.2026 01:15

Edited by author 13.04.2026 01:15

Edited by author 13.04.2026 01:18

Edited by author 13.04.2026 01:50

counterexample
4  0  0
-1 0  0
0  4  0
0  -6 0
It is invalid, but your your order is OK

#Finally did it. Now i see why indie games are so bugged
def Vect3d(start,end):  #int to int
    return (end[0]-start[0],end[1]-start[1],end[2]-start[2])
def multSc(vecta,vectb):#int to int
    rslt=0
    for i in (0,1,2):
        rslt+=vecta[i]*vectb[i]
    return rslt
def multVct(va,vb):     #int to int
    x=va[1]*vb[2]-va[2]*vb[1]
    y=va[2]*vb[0]-va[0]*vb[2]
    z=va[0]*vb[1]-va[1]*vb[0]
    return (x,y,z)
                       #vc=t*va+z*vb
def TZbool(va,vb,vc):  #always int and bool, no division
    mtrx=[[0,0,0],[0,0,0],[0,0,0]]
    for i in (0,1,2):
        mtrx[i][0]=va[i]
        mtrx[i][1]=vb[i]
        mtrx[i][2]=vc[i]
    c1=0
    r1=0
    while c1<2:
        if mtrx[r1][c1]!=0:
            for r2 in (0,1,2):
                if r2!=r1:
                    for c2 in (0,1,2):
                        if c2!=c1:
                            mtrx[r2][c2]=mtrx[r2][c2]*mtrx[r1][c1]-mtrx[r1][c2]*mtrx[r2][c1]
                    mtrx[r2][c1]=0
            c1+=1
        r1=(r1+1)%3
    #########################
    t=False             #t>=0
    for i in (0,1,2):   #only one mtrx[i][0]!=0 in solved 3x2 mtrx
        if (mtrx[i][0]>0 and mtrx[i][2]>=0) or (mtrx[i][0]<0 and mtrx[i][2]<=0):
            t=True
    z=False             #z>=0
    for i in (0,1,2):
        if (mtrx[i][1]>0 and mtrx[i][2]>=0) or (mtrx[i][1]<0 and mtrx[i][2]<=0):
            z=True
    return t and z

A=tuple(map(int,input().split()))
B=tuple(map(int,input().split()))
C=tuple(map(int,input().split()))
D=tuple(map(int,input().split()))
goNext=True
if goNext:              #check if turning 90
    AB=Vect3d(A,B)
    DC=Vect3d(D,C)
    if multSc(AB,DC)!=0:
        goNext=False
        print('Invalid')
if goNext:              #check if AB and CD intersect
    AD=Vect3d(A,D)
    if multSc(AD,multVct(AB,DC))!=0:
        goNext=False
        print('Invalid')
if goNext:
    BC=Vect3d(B,C)
    CD=Vect3d(C,D)      # -DC
    if TZbool(AB,CD,BC):
        print('Valid')
    else:
        print('Invalid')

Edited by author 14.04.2026 01:12