M - Intersection of Line Segments
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
xy -平面上に 2 つの線分があります。 i 番目の線分の端点は座標 (a_i,b_i) と座標 (c_i,d_i) です。
これら 2 つの線分が交点を持つかどうかを判定してください。
制約
- -1000 \leq a_i,b_i,c_i,d_i \leq 1000
- (a_i,b_i)\neq (c_i,d_i)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2
出力
2 つの線分が交点を持つならば Yes と、持たないならば No と出力せよ。
入力例 1
0 0 10 10 0 10 10 0
出力例 1
Yes
下図のように、2 つの線分は座標 (5,5) で交わります。
入力例 2
0 0 10 0 0 10 0 0
出力例 2
Yes
入力例 3
0 0 10 0 0 10 0 1
出力例 3
No
入力例 4
0 3 8 7 0 3 8 7
出力例 4
Yes
Problem Statement
There are two line segments in the xy-plane. The endpoints of the i-th line segment are at coordinates (a_i,b_i) and (c_i,d_i).
Determine if these two line segments intersect.
Constraints
- -1000 \leq a_i,b_i,c_i,d_i \leq 1000
- (a_i,b_i)\neq (c_i,d_i)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2
Output
Print Yes if the two line segments intersect, and No otherwise.
Sample Input 1
0 0 10 10 0 10 10 0
Sample Output 1
Yes
As shown below, the two line segments intersect at coordinates (5,5).
Sample Input 2
0 0 10 0 0 10 0 0
Sample Output 2
Yes
Sample Input 3
0 0 10 0 0 10 0 1
Sample Output 3
No
Sample Input 4
0 3 8 7 0 3 8 7
Sample Output 4
Yes