三点定圆
已知三个不在同一直线上的点 \((x_1, y_1), (x_2, y_2), (x_3, y_3)\)。请确定过此三点的圆的圆心。
设圆心为 \((x, y)\)，半径为 \(r\)，则圆的方程为
\[(x_i-x)^2+(y_i-y)^2=r^2 \]展开得到
\[x_i^2-2x_ix+x^2+y_i^2-2y_iy+y^2=r^2 \]我们并不需要现在得知 \(r\) 的具体值，即我们并不关心 \(r^2\)。不妨把未知数的平方项合并为一个常数 \(C\)。
\[2x_ix+2y_iy+C=x_i^2+y_i^2 \]即我们现在需要求这个方程组的解：
\[\begin{bmatrix} x_1& y_1& 1\\ x_2& y_2& 1\\ x_3& y_3& 1\\ \end{bmatrix}\times \begin{bmatrix} 2x\\ 2y\\ C\\ \end{bmatrix}= \begin{bmatrix} x_1^2+y_1^2\\ x_2^2+y_2^2\\ x_3^2+y_3^2\\ \end{bmatrix} \]根据克莱默法则，我们只需要求三个三阶行列式。
考虑到这三个行列式的最右边都是一列 \(1\)，不妨将行列式沿着 \(1\) 展开，如：
\[\begin{vmatrix} x_1& y_1& 1\\ x_2& y_2& 1\\ x_3& y_3& 1\\ \end{vmatrix}= \begin{vmatrix} x_2& y_2\\ x_3& y_3\\ \end{vmatrix}- \begin{vmatrix} x_1& y_1\\ x_3& y_3\\ \end{vmatrix}+ \begin{vmatrix} x_1& y_1\\ x_2& y_2\\ \end{vmatrix} \]也就稍微好写一点点。
最小圆覆盖
先看算法流程：
shuffle(a + 1, a + n + 1, mt19937{random_device{}()});
dot O = a[1];
double r = 0;
for (int i = 2; i <= n; i++) {
if (dis(a[i], O) - r < eps) continue; // 在圆内
O = a[i], r = 0;
for (int j = 1; j < i; j++) {
if (dis(a[j], O) - r < eps) continue;
O = (a[i] + a[j]) / 2, r = dis(a[i], a[j]) / 2;
for (int k = 1; k < j; k++) {
if (dis(a[k], O) - r < eps) continue;
O = minCircle(a[i], a[j], a[k]), r = dis(O, a[i]);
}
}
}
注意枚举顺序，\(i, j, k\) 都是从小往大枚举。
正确性证明
https://www.luogu.com.cn/article/8imn9rtw 不想抄了。这里补充最后一步的依据，是这个引理。
存在 \(
标签：begin,end,覆盖,复杂度,最小,vmatrix,bmatrix,模板 From： https://www.cnblogs.com/caijianhong/p/18322254/template-mincircle