DP

Thank you! This test helped me a lot. And I've got AC. (I used 'decimal' with 100 digits in Python and Newton-Cotes method with n=8.)

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

> My algo is as follows:
> 1.for any contestant i:
> 2.     if(there is a contestant j whose three speeds all equal to
i )
> 3.     then   i and j are both sure losers;
> 4.     else if(the three speeds of j are no less than i)
> 5.     then   i is a sure loser;
> 6.     else if(the three speeds of j are no more than i)
> 7.     then   j is a sure loser;
> 8.for any contestant i:
> 9.     if(i is a sure loser) writeln(No);
> 10.    else writeln(Yes);
>

4
10000 10000 1
10000 1 10000
1 10000 10000
2 2 2

the fourth contestant is not a "sure loser" but always lose...

The correct answer is:

No
Yes
Yes

No
No

Because they are tied regardless of what the judge chooses.

The correct answers are:

No
No
Yes
Yes

and

No
No
Yes

Really, i've got AC with incorrect answer for this test. I used too small infinity (1e10).

this test is incorrect !

9999a + 9999b + 1c > 10000a + 9998b + 10000c
9999a + 9999b + 1c > 9998a + 10000b + 10000c
=> 19998a+19998b+2c > 19998a+19998b+ 20000c
=> 2c > 20000c !!!!
that why the answer is:
No
Yes
Yes

The second and eighth tests are invalid.
The second test contains a concave polygone.
The eighth test contains a repeating vertex.

The second test fixed:
3 4
0 2000 1000 3000 0 3000
0 0 3000 0 3000 3000 0 3000
ans: 647.1067811865

The eighth test fixed:
4 3
0 0 3000 0 3000 3000 0 3000
-1000 2000 1000 -1000 2000 -1000
ans: 647.1067811865

Why is the answer not "ABCD" in this case?

YES, why is not ABCD

idk
i just love chiken wings so much

Edited by author 19.11.2025 14:03