Oiclass PUJI Circle 题解

泰裤辣！解析几何

引

首先我们看题，发现题目会给我们四个点，让我们判断这四个点是否共圆，那么如何判断这四个点是否共圆呢？我的思路是这样的：

首先以这四个点为顶点随便画出两个不同的三角形，求这两个三角形的外心
然后判断这两个外心是否相同，如果是的话，那么我们可以判断这四个点事共圆的

那么这种思路就会引起很多问题了，首先什么是外心？很巧，今天数学课数学老师留的思考题就是如何找到三角形的外心，也就是一个可以让三角形三个顶点都与圆相切的圆的圆心，或者你也可以理解为一个到三角形三个顶点距离都相等的点，那么究竟如何找到这个点呢？

思考了很久很久（一中午）突然恍然大悟，发现三角形三条边所对应的中垂线的交点就是三角形的外心！Ohhhhhh~ 那我们是不是解决问题了？不，不是，好戏才刚刚开始。

这种方法就引出了很多很多的问题：

如何求得中垂线的解析式？
如何求三线的交点？

首先我们来解决第一个

如何求得中垂线的解析式？

我们首先要了解中垂线的定义，根据百度百科的说法，中垂线，又称垂直平分线是指经过某一条线段的中点，并且垂直于这条线段的直线。垂直平分线可以看成到线段两个端点距离相等的点的集合，垂直平分线是线段的一条对称轴。好的，那么也就是说中垂线就是过一线段终点所作的平行于该线段的直线，查阅教科书可知，对于由点 $A(x_1, y_1)$ 和点 $B(x_2, y_2)$ 构成的线段 $AB$ 的中垂线的方程，也称为中垂线方程为 \[ y - \frac{y_1 + y_2}{2}=-\frac{x_1 - x_2}{y_1 - y_2}·\left(x - \frac{x_1 + x_2}{2}\right) \] 那么这条方程是怎么得来的呢？

首先我们知道，线段$AB$ 的中点$C$ 应该符合中点公式：$C\left(\frac{x_1 + x_2}{2}, \frac{y_1 + y_2}{2}\right)$ ，这是所有初中生都懂得一点。

然后我们会利用到解析几何中的一条关于两直线垂直的性质：已知两直线 $y = k_1x + b_1$ 与 $y = k_2x + b_2$ 相互垂直，那么 $k_1 \times k_2=-1$ 或者你也可以理解为，两直线垂直，其斜率互为负倒数。

这时候又产生了一个问题，为什么存在这个性质呢？

为了解决这个问题，我们需要证明一个猜想：两直线垂直，斜率互为负倒数 。（注意，这里的部分证明过程参考知乎用户双木止月Tong 的文章《中垂线》）

证明过程： \[ \begin{array}{l} 证明:\\ 取直线\ l_1\ 的方向向量\ (1, k_1)\ ,直线\ l_2 \ 的方向向量\ (1, k_2) \\ \because l_1 \perp l_2\\ \therefore (1, k_1) \cdot (1, k_2)=1 \times 1 + k_1 \times k_2 = 0\\ \therefore k_1 \cdot k_2 = -1\\ 结论得证 \end{array} \]

好了，那么现在我们拥有了这一条公式和一条性质，那么要怎样写出这一条方程呢？

因为线段$AB$ 的斜率为 $ k = $ ，所以中垂线的斜率应该为 $-\frac{1}k{} = -\frac{x_1 - x_2}{y_1 - y_2}$ ，又因为线段$AB$ 的中点坐标为 $ (, )$ 所以根据直线点斜式（$y - b = k(x - a)$）可得： $ y - =-·(x - )$ 。至此，我们成功的得到了方程，但是为了更方便程序的编写与 DEBUG 我们将方程改写为 $ax + by + c = 0$ 的形式： \[ \frac{x_1 - x_2}{y_1 - y_2} \cdot x + y - \frac{y_1 + y_2}{2} - \frac{x_1 + x_2}{2} \cdot \frac{x_1 - x_2}{y_1 - y_2} = 0 \]

又根据平方差公式 $a^2 - b^2 = (a + b) \cdot (a - b)$ ，我们可以将方程进一步化简为： \[ \frac{x_1 - x_2}{y_1 - y_2} \cdot x + y - \frac{y_1 + y_2}{2} - \frac{(x_1)^2 - (x_2)^2}{2y_1 - 2y_2} = 0 \]

好的，那么关于中垂线解析式的问题，我们已经完全解决了，next one ~

\[ ax + by + c = 0 \]

如何求三线的交点？

首先我们要明确交点的代数意义，对于两条直线 $a_1x + b_1y + c_1 = 0$ 和 $a_2x + b_2y + c_2 = 0$，如果你在坐标系 $xOy$ 中把他画出来，你就会发现，交点实际上就是同时符合两条方程的 $x$ 与 $y$ 所对应的坐标，也就是说，如果我们联立这两条线性方程（一次方程）得到一个线性方程组（一次方程组），交点的坐标就是该线性方程组的解所对应的点。

那么我们现在联立这两条方程得到这样一个方程组： \[ \left\{ \begin{array}{l} a_1x + b_1y + c_1 = 0\\ a_2x + b_2y + c_2 = 0 \end{array} \right. \] 然后十分艰难的解出来（用了10 张草稿纸，算了 5 遍 ┭┮﹏┭┮），就会得到： \[ \left\{ \begin{array}{l} x = \frac{b_2 \cdot c_1 - b_1 \cdot c_2} {a_2 \cdot b_1 - a_1 \cdot b_2}\\ y = -\frac{a_1x + c_1}{b_1} \end{array} \right. \]

那么三条线的交点怎么求呢？实际上，我们根本不需要求三条线的交点，我们只需要求两条线的交点即可，因为我们两条中垂线是交于一点的，而三条中垂线依然是交于一点，所以我们可以发现，只需要两条中垂线就可以确定一个三角形的外心。

下班（才怪）！！！

实现

我们现在已经掌握了理论知识，下面是实现的过程。

首先我们需要定义两个结构体，分别名为 dot 和 line 用于存储点和线，实现如下：

struct dot {
    // x 坐标， y 坐标
    double x, y;
	
    // 计算与其他点的距离（勾股定理）
    double dis(const dot a) const {
        return sqrt((a.x - x) * (a.x - x) + (a.y - y) * (a.y - y));
    }
	
    // 判断点是否相等
    bool operator==(const dot a) const {
        return abs(a.x - x) <= 0.3 || abs(a.y - y) <= 0.3;
    }
};

struct line {
    // a, b, c 对应 ax + by + c = 0 中的 a, b, c
    double a, b, c;
};

然后只要把各种公式实现以下即可，全部代码：

#include <iostream>
#include <cmath>

using namespace std;

struct dot {
    // x 坐标， y 坐标
    double x, y;

    // 计算与其他点的距离（勾股定理）
    double dis(const dot a) const {
        return sqrt((a.x - x) * (a.x - x) + (a.y - y) * (a.y - y));
    }

    // 判断点是否相等
    bool operator==(const dot a) const {
        return abs(a.x - x) <= 0.3 || abs(a.y - y) <= 0.3;
    }
};

struct line {
    // a, b, c 对应 ax + by + c = 0 中的 a, b, c
    double a, b, c;
};

// 根据两个点获得中垂线
line get_mid_perpendicular(dot a, dot b) {
    return (line) {
            (a.x - b.x) / (a.y - b.y),
            1,
            -(a.y + b.y) / 2 - (a.x * a.x - b.x * b.x) / (2 * a.y - 2 * b.y)
    };
}

// 计算交点
dot get_intersection(line a, line b) {
    double a1 = a.a, a2 = b.a, b1 = a.b, b2 = b.b, c1 = a.c, c2 = b.c;
    double x = (b2 * c1 - b1 * c2) / (a2 * b1 - a1 * b2), y = -(a1 * x + c1) / b1;
    return (dot) {x, y};
}

// 计算外心
dot get_circumcenter(dot a, dot b, dot c) {
    line mid_perpendicular1 = get_mid_perpendicular(a, b), mid_perpendicular2 = get_mid_perpendicular(b, c);
    return get_intersection(mid_perpendicular1, mid_perpendicular2);
}

dot a[5];

int main() {
    for (int i = 1; i <= 4; i++) {
        cin >> a[i].x >> a[i].y;
    }
    dot circumcenter1 = get_circumcenter(a[1], a[2], a[3]), circumcenter2 = get_circumcenter(a[1], a[2], a[4]);
    if (circumcenter1 == circumcenter2) {
        cout << 1 << " ";
        printf("%.6f %.6f %.6f", (circumcenter1.x), (circumcenter1.y), (circumcenter1.dis(a[1])));
    } else {
        cout << 2 << " ";
        printf("%.6f %.6f %.6f", (circumcenter1.x), (circumcenter1.y), (circumcenter1.dis(a[1])));
    }
}

#题解 #OiClass

Oiclass PUJI Circle 题解

https://lixuannan.github.io/posts/19144

作者

CodingCow Lee

发布于

2023年5月13日

许可协议

MCOI 2023年6月月赛题解上一篇

Oiclass PUJI 971 题解下一篇