[python] ABC016 D交差判定のエラーが取れない

前提・実現したいこと

下記の問題に回答をしているのですが、半分のケースで誤答が出ます
基本的には「多角形の辺と与えられた直線の交点/2 + 1」が解答だと理解していますが、どこが違うでしょうか・・・？

該当のソースコード

python
1
2#交差しているか判定。Trueでに直線が交差
3def kousa(xa, ya, xb, yb, xc, yc, xd, yd):
4    s = (xa-xb)*(yc-ya) - (ya-yb)*(xc-xa)
5    t = (xa-xb)*(yd-ya) - (ya-yb)*(xd-xa)
6
7    if s*t <= 0:
8        return True
9    else:
10        return False
11
12
13def main():
14    xa, ya, xb, yb = map(int, input().split())
15    N = int(input())
16
17    inlis = []
18
19    for _ in range(N):
20        x, y = map(int, input().split())
21        inlis.append([x,y])
22    
23    kouten = 0
24
25    for i in range(-1, N-1):
26        xc, yc = inlis[i]
27        xd, yd = inlis[i+1]
28        
29        if kousa(xa,ya,xb,yb,xc,yc,xd,yd):
30            kouten += 1
31    
32    print(1+kouten//2)
33
34
35
36if __name__ == "__main__":
37    main()
38

試したこと

色々思いつくコーナーケースを試していますが、どれもうまくいきませんでした
恐れ入りますが、ご助言いただけますと幸いです

行動規範の内容に同意します

回答1件

自己解決

すいません、解決しました。交差の判定が足りていませんでした
下記で正解が出ました。ありがとうございました

python
1
2def kousa(xa, ya, xb, yb, xc, yc, xd, yd):
3    s = (xa-xb)*(yc-ya) - (ya-yb)*(xc-xa)
4    t = (xa-xb)*(yd-ya) - (ya-yb)*(xd-xa)
5
6    u = (xc -xd) * (ya-yc) - (yc-yd) * (xa-xc)
7    v = (xc-xd) * (yb-yc) - (yc-yd) * (xb-xc)
8
9    if s*t <= 0 and u*v <= 0:
10        return True
11    else:
12        return False
13