提出 #78140658

ソースコード 拡げる

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int main(void) {
  int T, tc;
  if (scanf("%d", &T) != 1) return 1;
  for (tc = 0; tc < T; tc++) {
    int Px, Py, Qx, Qy, Rx, Ry, Sx, Sy;
    long long a, b, c, d, e, f;
    if (scanf("%d%d%d%d%d%d%d%d", &Px, &Py, &Qx, &Qy, &Rx, &Ry, &Sx, &Sy) != 8) return 1;
    a = 2LL * Px - 2LL * Qx;
    b = 2LL * Py - 2LL * Qy;
    c = (long long)Px * Px + (long long)Py * Py - (long long)Qx * Qx - (long long)Qy * Qy;
    d = 2LL * Rx - 2LL * Sx;
    e = 2LL * Ry - 2LL * Sy;
    f = (long long)Rx * Rx + (long long)Ry * Ry - (long long)Sx * Sx - (long long)Sy * Sy;
    if (b * d == a * e) {
      if (
        a == 0
          ? (__int128_t)c * e == (__int128_t)b * f
          : (__int128_t)c * d == (__int128_t)a * f
      ) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int main(void) {
	int T, tc;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 0; tc < T; tc++) {
		int Px, Py, Qx, Qy, Rx, Ry, Sx, Sy;
		long long a, b, c, d, e, f;
		if (scanf("%d%d%d%d%d%d%d%d", &Px, &Py, &Qx, &Qy, &Rx, &Ry, &Sx, &Sy) != 8) return 1;
		a = 2LL * Px - 2LL * Qx;
		b = 2LL * Py - 2LL * Qy;
		c = (long long)Px * Px + (long long)Py * Py - (long long)Qx * Qx - (long long)Qy * Qy;
		d = 2LL * Rx - 2LL * Sx;
		e = 2LL * Ry - 2LL * Sy;
		f = (long long)Rx * Rx + (long long)Ry * Ry - (long long)Sx * Sx - (long long)Sy * Sy;
		if (b * d == a * e) {
			if (
				a == 0
					? (__int128_t)c * e == (__int128_t)b * f
					: (__int128_t)c * d == (__int128_t)a * f
			) {
				/* 垂直二等分線は重なる */
				puts("Yes");
			} else {
				/* 垂直二等分線は重ならず平行 */
				puts("No");
			}
		} else {
			/* 垂直二等分線が平行でない */
			puts("Yes");
		}
	}
	return 0;
}

/*

Yes iff
線分 (P_x, P_y) - (Q_x, Q_y) の垂直二等分線と、
線分 (R_x, R_y) - (S_x, S_y) の垂直二等分線が共通点を持つ

すなわち、一致 or 並行でない (傾きが違う)

(P_x - x)**2 + (P_y - y)**2 == (Q_x - x)**2 + (Q_y - y)**2

P_x**2 - 2*P_x*x + x**2 + P_y**2 - 2*P_y*y + y**2
== Q_x**2 - 2*Q_x*x + x**2 + Q_y**2 - 2*Q_y*y + y**2

(2*P_x - 2*Q_x)*x + (2*P_y - 2*Q_y)*y == P_x**2 + P_y**2 - Q_x**2 - Q_y**2

同様に
(2*R_x - 2*S_x)*x + (2*R_y - 2*S_y)*y == R_x**2 + R_y**2 - S_x**2 - S_y**2

これを
a*x + b*y == c … (1)
d*x + e*y == f … (2)
とする

平行 → (1) を d/a 倍して、左辺が (2) と一致する (ただし a != 0 のとき)
すなわち b * d / a == e
変形して b * d == a * e

a == 0 のときは、(P_x, P_y) と (Q_x, Q_y) は異なるので、必ず垂直二等分線はできる
ため、b != 0 のはずなので、d == 0 のとき、かつそのときのみこれを満たす
これは、2直線が平行であることになる
よって、a == 0 のときもこの式で判定できる

平行のとき、同一性判定をする
a != 0 のとき c * d / a == f すなわち c * d == a * f
a == 0 のとき c * e / b == f すなわち c * e == b * f

*/

提出情報

ジャッジ結果