壊すとword│E-olv

menu icon

CF 77E Martian Food

2015.01.09 17:41 Fri| 4 visits oi_2015| 2015_刷题日常| Text

Solution

这道题用到了圆的反演相关内容。

如图所示，以点 $B$ 为反演中心，在 $(0, r)$ 内取一合适的长度 $BD$ 为反演半径，进行反演变换，则原图中过 $B$ 点的圆 $c_1$、 $c_2$ 分别被反演为了两条互相平行的直线 $c_1'$ 和 $c_2'$， 而圆 $c_3$ 与两圆相切，反演后同样分别与两条直线相切。之后加入的每个小圆即依次向上排列。

以样例一为例，以点 $B$ 为坐标原点，我们可以在 $\mathcal O(1)$ 的时间内求出圆 $P_1'$ 的圆心坐标和半径，只需反演回原图中即可得答案（用红色标出）。

由公式得， $P_1P_2 = BD^2 {P_1'P_2' \over BP_1'^2 - P_1'P_2'^2} $ 。于是易得下列代码

Code

#include <bits/stdc++.h>
#define sqr(x) ((x)*(x))

using namespace std;

int t, k;
double R, r;

int main()
{
    cin >> t;
    cout << fixed << setprecision(10);
    while (t--)
    {
        cin >> R >> r >> k;
        double a = (R + r) * r / (4 * R), b = k * (R - r) * r / (2 * R);
        double len = (R - r) * r / (4 * R);
        cout << len / (sqr(a) + sqr(b) - sqr(len)) * sqr(r) << '\n';
    }
}

化简，即得最终代码

Code

#include <bits/stdc++.h>
#define sqr(x) ((x)*(x))

using namespace std;

int t, k;
double R, r;

int main()
{
    cin >> t;
    cout << fixed << setprecision(10);
    while (t--)
    {
        cin >> R >> r >> k;
        double a = R + r, b = 2 * k * (R - r);
        double len = R - r;
        cout << 4 * R * r * len / (sqr(a) + sqr(b) - sqr(len)) << '\n';
    }
}
Newer