この問題は円そのものではなく 円の中心 が存在できる場所に注目することがポイントです。

円 \(C_1, C_2\) の中心を \(O\) とおきます。 点 \(P,Q\) はともに \(C_1\) の円周上にあるため、

\[OP = OQ\]

である必要があります。 2 点 \(P,Q\) からの距離が等しい点の集合は、線分 \(PQ\) の垂直二等分線です。よって、\(O\) は線分 \(PQ\) の垂直二等分線上(これを \(L_1\) とおきます)にあります。
同様の議論を \(R,S\) に適用することで、\(O\) は線分 \(RS\) の垂直二等分線上(これを \(L_2\) とおきます)にあります。
よって、\(O\) は \(L_1\) と \(L_2\) の共有点上である必要があります。逆に、そのような点が存在すればその点を中心として問題文の条件を満たす円 \(C_1, C_2\) を書けることは明らかです。
よって、今回の問題は以下の問題に言い換えられることが分かります。

線分 \(PQ\) の垂直二等分線 \(L_1\) と、線分 \(RS\) の垂直二等分線 \(L_2\) は共有点を持つか？

ここで、2 本の直線に関する事実として以下のことが知られています。

• 平行でない 2 直線は必ず交点を持つ。
• 異なる平行な 2 直線は必ず交点を持たない。

よって、言い換えた後の問題の答えは以下の通りです。

1. \(L_1\) と \(L_2\) が平行でない場合：平行でない 2 直線は必ず交点を持つので答えは Yes です。
2. \(L_1\) と \(L_2\) が平行である場合：\(L_1\) と \(L_2\) が同じ直線である場合は Yes で、そうでない場合は No です。

答えの出し方はわかったので、あとは

• \(L_1\) と \(L_2\) が平行かどうか
• \(L_1\) と \(L_2\) が同じかどうか

を計算できれば答えがわかります。そのために \(L_1, L_2\) の直線の式を求めてみましょう。

線分 \(PQ\) の 垂直二等分線 \(L_1\) の式を直接求めてみます。\(L_1\) 上の点 \((x,y)\) は \(P\) との距離と \(Q\) との距離が等しいので、\(L_1\) として以下の式が得られます。

\[(x-P_x)^2 + (y-P_y)^2 = (x - Q_x)^2 + (y - Q_y)^2\]

この式を整理すると

\[2(Q_x - P_x) x + 2 (Q_y - P_y) y + {P_x}^2 + {P_y}^2 - {Q_x}^2 - {Q_y}^2 = 0\]

という \(L_1\) に関する整数係数の直線の式が得られます。同様にして \(L_2\) に関する整数係数の直線の式も得られます。

式が複雑なので、新たな文字を用意して \(L_1, L_2\) を \(a_1 x + b_1 y + c_1 = 0, a_2 x + b_2 y + c_2 = 0\) と表すことにしましょう。

\(L_1\) と \(L_2\) が平行であることは \(a_1 b_2 - a_2 b_1 = 0\) であることと同値です。よってこの計算を行えば \(L_1\) と \(L_2\) が平行であるかを判定することが出来ます。
\(L_1\) と \(L_2\) が平行である場合、2 本の直線が完全に一致するかを判定する必要があります。これは直感的には \(a_1 = a_2, b_1=b_2, c_1=c_2\) が成り立つかを判定すればよさそうですが、例えば \((a_1,b_1,c_1)=(1,2,3), (a_2,b_2,c_2)=(2,4,6)\) である場合、2 本の直線が同じであることの判定に失敗してしまいます。
解決策はいくつかありますが、ここでは直線を標準化して持つ方針を取ります。標準化とは、1 個の直線に 1 個の表現(標準形と呼びます)を対応させて、直線をその表現に揃えることを言います。
例えば、以下の条件を全て満たす時に \(ax+by+c=0\) が標準化されている直線であると考えることにします。

• \(a,b,c\) は全て整数である。
• \(\gcd(a,b,c)=1\) である。
• \(a \neq 0\) の時、\(a \gt 0\) である。
• \(a = 0\) の時、\(b \gt 0\) である。

このように標準形を定義すると、任意の整数係数の直線に対して \(1\) 個の標準形が対応します。 よって \(\mathrm{gcd}\) の計算などを経て \(L_1, L_2\) を標準形に揃えてから、\(a_1 = a_2, b_1=b_2, c_1=c_2\) を判定すれば \(L_1\) と \(L_2\) が同じ直線であるかを判定できます。
以上の内容を適切に実装出来れば今回の問題を解くことが出来ます。

• 実装例(C++)

#include <iostream>
#include <numeric>
#include <tuple>
using namespace std;

tuple<long long, long long, long long> get_canonical(long long px, long long py,
                                                     long long qx,
                                                     long long qy) {
  long long a = 2 * (qx - px);
  long long b = 2 * (qy - py);
  long long c = px * px + py * py - qx * qx - qy * qy;
  long long g = gcd(a, gcd(b, c));
  a /= g, b /= g, c /= g;
  if (a < 0) a = -a, b = -b, c = -c;
  if (a == 0 and b < 0) b = -b, c = -c;
  return {a, b, c};
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    long long px, py, qx, qy, rx, ry, sx, sy;
    cin >> px >> py >> qx >> qy >> rx >> ry >> sx >> sy;
    auto [a1, b1, c1] = get_canonical(px, py, qx, qy);
    auto [a2, b2, c2] = get_canonical(rx, ry, sx, sy);
    if (a1 * b2 - a2 * b1 == 0) {
      if (a1 == a2 and b1 == b2 and c1 == c2) {
        cout << "Yes" << "\n";
      } else {
        cout << "No" << "\n";
      }
    } else {
      cout << "Yes" << "\n";
    }
  }
}