C5-D 外接圆

题目描述

小 A 想给小 B 寄几盒蒜。

R2R^2 平面上有五个特殊点$ A,B,C,D,E$，任意两点不重合，任意三点不共线。

小 A 可以任意选择 A,B,C,D,E{A,B,C,D,E} 中不同的三个点 P1,P2,P3P_1,P_2,P_3，并记 △P1P2P3△P_1P_2P_3 的外接圆为 C。小 A 只能在 C 上移动。

记以 ${A,B,C,D,E}∖{P_1,P_2,P_3} $中剩余的两个点 P4,P5P_4,P_5 所在的直线为 ℓ。小 B 只能在 ℓ 上移动。

小 A 想最小化两人之间的最短距离，使得寄蒜所支付的邮费最少。形式化地说，你需要求出 minC,ℓminP∈C,Q∈ℓ∣PQ∣min_{C,ℓ}min_{P∈C,Q∈ℓ}|PQ|，其中 ∣PQ∣=(xP−xQ)2+(yP−yQ)2|PQ|=\sqrt{(x_P−x_Q)^2+(y_P−y_Q)^2}为线段 $PQ $的欧几里得距离。

输入

本题测试点包含多组数据。

第一行，一个正整数$ T（1≤T≤10^4）$，表示数据组数。

对于每组数据：

一行，10 个整数 xA,yA,xB,yB,xC,yC,xD,yD,xE,yE（−103≤x,y≤103）x_A,y_A,x_B,y_B,x_C,y_C,x_D,y_D,x_E,y_E（−10^3≤x,y≤10^3），表示点 A,B,C,D,EA,B,C,D,E 的坐标。

输出

对于每组数据：

一行，一个实数，表示 minC,ℓminP∈C,Q∈ℓ∣PQ∣min_{C,ℓ}min_{P∈C,Q∈ℓ}|PQ|。答案保留三位小数。

输入样例

1
2
1
-5 0 -3 4 0 5 3 4 5 0

输出样例

1
0.000

提示

样例中给定的五个点共圆，因此无论如何选择$ P_1,P_2,P_3$，C 与 ℓ 都交于 P4,P5P_4,P_5，从而答案为 0.000。

题目分析

遍历所有外接圆的情况，求出圆心到直线的距离再减去半径，最后取最小值即可。

如果存在圆与直线香蕉的情况直接输出0.000。

三点求外接圆

1
2
3
4
5
6
7
8
9
10
Circle CircumscribedCircle(Point A, Point B, Point C)
{ // 外接圆
    double d = 2 * (A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y));
    if (dcmp(d) <= 0)
        return Circle(Point(0, 0), 0); // 三点共线
    double x = ((A.x * A.x + A.y * A.y) * (B.y - C.y) + (B.x * B.x + B.y * B.y) * (C.y - A.y) + (C.x * C.x + C.y * C.y) * (A.y - B.y)) / d;
    double y = ((A.x * A.x + A.y * A.y) * (C.x - B.x) + (B.x * B.x + B.y * B.y) * (A.x - C.x) + (C.x * C.x + C.y * C.y) * (B.x - A.x)) / d;
    Point O = Point(x, y);
    return Circle(O, Length(O - A));
}

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const double INF = 1e18;
const double EPS = 1e-9;

struct Point
{
    ll x, y;
};

// 计算三点的外接圆，返回是否存在外接圆
bool getCircumcircle(const Point &A, const Point &B, const Point &C, pair<pair<double, double>, double> &circle)
{
    double a1 = B.x - A.x;
    double b1 = B.y - A.y;
    double a2 = C.x - A.x;
    double b2 = C.y - A.y;

    double d = 2.0 * (a1 * b2 - a2 * b1);
    if (abs(d) < EPS)
        return false; // 共线，无外接圆

    double c1 = a1 * (A.x + B.x) + b1 * (A.y + B.y);
    double c2 = a2 * (A.x + C.x) + b2 * (A.y + C.y);

    double xc = (b2 * c1 - b1 * c2) / d;
    double yc = (a1 * c2 - a2 * c1) / d;

    double r = sqrt((xc - A.x) * (xc - A.x) + (yc - A.y) * (yc - A.y));

    circle = {{xc, yc}, r};
    return true;
}

// 计算点到直线的距离
double distancePointToLine(double x, double y, double A, double B, double C)
{
    return abs(A * x + B * y + C) / sqrt(A * A + B * B);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        Point pts[5];
        for (int i = 0; i < 5; i++)
            cin >> pts[i].x >> pts[i].y;
        double min_dist = INF;
        bool flag = false;
        for (int i = 0; i < 5; i++)
        {
            for (int j = i + 1; j < 5; j++)
            {
                for (int k = j + 1; k < 5; k++)
                {
                    // 确定剩余的两个点
                    vector<int> indices;
                    for (int m = 0; m < 5; m++)
                        if (m != i && m != j && m != k)
                            indices.push_back(m);
                    Point P1 = pts[i], P2 = pts[j], P3 = pts[k];
                    Point P4 = pts[indices[0]], P5 = pts[indices[1]];
                    // 计算外接圆
                    pair<pair<double, double>, double> circle;
                    if (!getCircumcircle(P1, P2, P3, circle))
                        continue; // 共线，无外接圆
                    double xc = circle.first.first;
                    double yc = circle.first.second;
                    double r = circle.second;
                    // 计算直线P4P5的一般式Ax + By + C = 0
                    double A = P5.y - P4.y;
                    double B = P4.x - P5.x;
                    double C = -(A * P4.x + B * P4.y);
                    // 计算圆心到直线的距离
                    double d = distancePointToLine(xc, yc, A, B, C);
                    if (d <= r + EPS)
                    {
                        min_dist = min(min_dist, 0.0);
                        flag = true;
                        break;
                    }
                    else
                    {
                        min_dist = min(min_dist, d - r);
                    }
                }
                if (flag)
                    break;
            }
            if (flag)
                break;
        }
        // 输出结果，保留三位小数
        printf("%.3lf\n", min_dist);
    }
}