CF 77E Martian Food
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'; } }