D - Concentric Circles Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

xy 平面上に以下の条件を全て満たす 2 個の円 C_1, C_2 は存在しますか？　ただし C_1, C_2 は同一である可能性があります。

  • 異なる 2 点 (P_x, P_y), (Q_x, Q_y) は C_1 の円周上にある。
  • 異なる 2 点 (R_x, R_y), (S_x, S_y) は C_2 の円周上にある。
  • C_1 と C_2 は中心が一致する。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \leq T \leq 5 \times 10^4
  • -10^9 \leq P_x,P_y,Q_x,Q_y,R_x,R_y,S_x,S_y \leq 10^9
  • (P_x, P_y) \neq (Q_x, Q_y)
  • (R_x, R_y) \neq (S_x, S_y)
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケース \mathrm{case}_t は以下の形式で与えられる。

P_x P_y Q_x Q_y R_x R_y S_x S_y

出力

T 行出力せよ。t 行目には t 番目のテストケースの答えを出力せよ。
各テストケースでは、条件を全て満たす 2 個の円 C_1, C_2 が存在する場合は Yes を、存在しない場合は No を出力せよ。

入力例 1

3
2 0 1 1 -1 0 1 2
1 0 -1 0 0 1 0 -1
4 0 3 1 2 0 1 1

出力例 1

Yes
Yes
No

1 番目のテストケースを考えます。以下の図に示す通り、中心が (1,0) で半径が 1 の円を C_1、中心が (1,0) で半径が 2 の円を C_2 とすると条件を満たします。

2 番目のテストケースでは、C_1 と C_2 をともに中心が (0,0) で半径が 1 の円とすると条件を満たします。

image

Score : 425 points

Problem Statement

Do there exist two circles C_1 and C_2 on the xy-plane satisfying all of the following conditions? Here, C_1 and C_2 may coincide.

  • The two distinct points (P_x, P_y) and (Q_x, Q_y) lie on the circumference of C_1.
  • The two distinct points (R_x, R_y) and (S_x, S_y) lie on the circumference of C_2.
  • C_1 and C_2 have the same center.

You are given T test cases; solve each of them.

Constraints

  • 1 \leq T \leq 5 \times 10^4
  • -10^9 \leq P_x,P_y,Q_x,Q_y,R_x,R_y,S_x,S_y \leq 10^9
  • (P_x, P_y) \neq (Q_x, Q_y)
  • (R_x, R_y) \neq (S_x, S_y)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case \mathrm{case}_t is given in the following format:

P_x P_y Q_x Q_y R_x R_y S_x S_y

Output

Output T lines. The t-th line should contain the answer to the t-th test case.
For each test case, output Yes if there exist two circles C_1 and C_2 satisfying all of the conditions, and No otherwise.

Sample Input 1

3
2 0 1 1 -1 0 1 2
1 0 -1 0 0 1 0 -1
4 0 3 1 2 0 1 1

Sample Output 1

Yes
Yes
No

Consider the first test case. As shown in the figure below, if we let C_1 be the circle with center (1,0) and radius 1, and C_2 be the circle with center (1,0) and radius 2, the conditions are satisfied.

For the second test case, letting both C_1 and C_2 be the circle with center (0,0) and radius 1 satisfies the conditions.

image