Mindis

Posted on | In , ,

题目链接

题意

已知一个圆和不在圆外的两个点P，Q，P和Q在同心圆上。
要求在圆上找一点使它到P和Q距离和最小。

思路

圆的反演裸题，也可以二分椭圆大小。

Code

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50

struct po
{
    double x, y;
    po(double _x = 0, double _y = 0): x(_x), y(_y) {}
};

double dis(po a, po b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        double R;
        scanf("%lf", &R);
        po P, Q;
        scanf("%lf%lf", &P.x, &P.y);
        scanf("%lf%lf", &Q.x, &Q.y);
        po zero = po(0, 0);
        double r = dis(zero, P);
        if (P.x == Q.x && P.y == Q.y)
        {
            printf("%.8f\n", (2 * (R - r)));
            continue;
        }    
        double k = R * R / r / r;
        po PP = po(P.x * k, P.y * k);
        po QQ = po(Q.x * k, Q.y * k);
        po mid = po((PP.x + QQ.x) / 2.0, (PP.y + QQ.y) / 2.0);
        if (dis(mid, zero) >= R)
        {
            po m = po((P.x + Q.x) / 2, (P.y + Q.y) / 2);
            double dm = dis(zero, m);
            po d = po(m.x * R / dm, m.y * R / dm);
            printf("%.10f\n", (dis(d, P) + dis(d, Q)));
        }
        else
        {
            double ans = dis(PP, QQ) * r / R;
            printf("%.10f\n", ans);
        }
    }
    return 0;
}
0%