356 . 線段相交
TopCoder
Description
在計算幾何中，線段是十分常出現在題目中的元素，舉凡計算長度，角度，相交，平行等。而要描述線段，最簡單容易的就是描述該線段的兩端點，便可清楚且唯一的表示某個線段。
現在你很好奇，給定兩條線段 $P,Q$，線段 $P$ 與線段 $Q$ 是否有相交。此處交點若在頂點上亦視爲相交。
Input Format
第一行包含一個整數 $T$，表示接下來包含 $T$ 對線段 $P,Q$。
接著包含 $T$ 行，每行包含八個整數 ${P_1}_x,{P_1}_y,{P_2}_x,{P_2}_y,{Q_1}_x,{Q_1}_y,{Q_2}_x,{Q_2}_y$ 分別代表線段 $P$ 的兩端點座標，以及線段 $Q$ 的兩端點座標。
- $1 \le T \leq 10^ 5$
- $0 \le |{P_1}_x|,|{P_1}_y|,|{P_2}_x|,|{P_2}_y|,|{Q_1}_x|,|{Q_1}_y|,|{Q_2}_x|,|{Q_2}_y| \le 10^ 9$
Output Format
對於每對線段 $P,Q$，若相交便輸出一行 $\texttt{Yes}$，否則輸出一行 $\texttt{No}$
Sample Input 1
3
0 0 2 0 0 1 2 1
0 0 2 0 1 1 1 -1
0 0 2 0 3 1 3 -1
0 0 2 0 0 1 2 1
0 0 2 0 1 1 1 -1
0 0 2 0 3 1 3 -1
Sample Output 1
No
Yes
No
Yes
No
Hints
Problem Source
NEOJ Problem 401
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | 100 |