ABC467D

XXh0919 · 2026-07-18 22:23:23 · 题解

upd on 2026.7.19：补充了有关于斜率计算的内容。

一眼秒题。

题意

给你四个点 P(p_x,p_y),Q(q_x,q_y),R(r_x,r_y),S(s_x,s_y)，问你是否存在两个圆 C_1,C_2 满足它们圆心相同且 P,Q 在 C_1 上，R,S 在 C_2 上。注意 C_1 可以和 C_2 重合。

解法

你只要学完了初中数学所有内容并了解了部分高中数学内容就应当可以秒掉。

容易发现 C_1 和 C_2 是同心圆。

考虑我们如何尺规作图作出一个圆。实际上我们取了三个不共线的点，然后将它们顺次连接得到两条线段，分别作这两条线段的垂直平分线交于一点，则这个点为圆心。

所以我们利用这个思想，分别算出线段 PQ 和线段 RS 的垂直平分线的斜率。显然可以构造圆心为两条直线的交点，而两条直线相交当且仅当它们不平行，所以我们直接判断它们斜率相不相等即可。

但是这样会忽略两条垂直平分线重合的情况。所以特判一下，如果 RS 的中点正好在 PQ 的垂直平分线上，说明两条垂直平分线重合，此时满足条件，否则不满足。具体就是你把 RS 中点 M_1(\frac{r_x+s_x}{2},\frac{r_y+s_y}{2}) 和 PQ 中点 M_2(\frac{p_x+q_x}{2},\frac{p_y+q_y}{2}) 的斜率 k_{M_1M_2} 算出来，然后看是不是和垂直平分线斜率相等，相等说明共线。

怎么算垂直平分线 l 的斜率：我们知道 k_{PQ}=\frac{p_y-q_y}{p_x-q_x}，显然 PQ 的垂直平分线垂直于 PQ，所以有 k_{PQ}\cdot k_l=-1，可得 k_l=-\frac{p_x-q_x}{p_y-q_y}，对于 RS 同理。那么两条垂直平分线有交点则要满足 -\frac{p_x-q_x}{p_y-q_y}\not=-\frac{r_x-s_x}{r_y-s_y}。对于重合的情况按照上面说的特判来做就行了。

温馨提示：注意精度问题，尽量不要用除法，用乘法代替算。

代码实现是把上面的一堆式子化简之后得到的。读者可以自己尝试化简一下。

:::success[Code]

i64 px, py, qx, qy, rx, ry, sx, sy;

inline void solve () {
    cin >> px >> py >> qx >> qy >> rx >> ry >> sx >> sy;
    if ((qy - py) * (rx - sx) != (ry - sy) * (qx - px)) cout << "Yes" << endl;
    //这里直接算的 PQ 和 RS 的斜率，因为你发现两条线段的垂直平分线斜率比较式化简之后就是这个东东
    else {
        i64 Axx = px + qx, Ayy = py + qy;
        i64 Bxx = rx + sx, Byy = ry + sy;
        if ((Ayy - Byy) * (qy - py) == (-qx + px) * (Axx - Bxx)) cout << "Yes" << endl;//垂直平分线重合
        else cout << "No" << endl;
    }
}

::: :::info[彩蛋] 下面这张图是我们学校参加了这场比赛的人的这个题的提交情况：

（没有提交的可以看作是不屑于做这个题）

状况十分惨烈啊。 :::