Yeah, thanks) I fixed it. Chess Battle Advanced

My AC solution says the answer is:
Yes

After further investigation, I was able to get to the bottom of things:

(1) My (ID 11182578 - WA #22) solution was indeed wrong and I was able to fix it (ID 11197306 - AC).
(2) My (ID 11182582 - AC) solution continues to give a completly different result on the above mentioned test.

Conclusions:
(1) To pass WA #22, I had to handle cases where the origin (0, 0, 0), when projected on the plane containing the triangle, would fall on one of the vertices or on one of the edges of the triangle.

(2) Since both of my AC solutions give widely different results on the above mentioned test it means the tests are weak and at least the above test should be added to the testset. The correct answer is the one returned by my (ID 11182578 - WA #22) and (ID 11197306 - AC) submissions.


For those who look for tests:
Input #1:
10 0 0
10 100 0
10 0 100

Output #1:
4999.748318598260


Input #2:
54 46 -161
-82 -150 -33
100 127 -175

Output #2:
37.855475851615

This is a very nice problem! I learned a lot from solving it. Good luck in your attempt!

easy 3 for)

Fixed

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.