CodeForces-77E(计算几何+笛卡尔定理)

比眉伴天荒 2022-06-09 08:47 324阅读 0赞

问题描述:

Have you ever tasted Martian food? Well, you should.

Their signature dish is served on a completely black plate with the radius of R, flat as a pancake.

First, they put a perfectly circular portion of the Golden Honduras on the plate. It has the radius of r and is located as close to the edge of the plate as possible staying entirely within the plate. I. e. Golden Honduras touches the edge of the plate from the inside. It is believed that the proximity of the portion of the Golden Honduras to the edge of a plate demonstrates the neatness and exactness of the Martians.

Then a perfectly round portion of Pink Guadeloupe is put on the plate. The Guadeloupe should not overlap with Honduras, should not go beyond the border of the plate, but should have the maximum radius. I. e. Pink Guadeloupe should touch the edge of the plate from the inside, and touch Golden Honduras from the outside. For it is the size of the Rose Guadeloupe that shows the generosity and the hospitality of the Martians.

Further, the first portion (of the same perfectly round shape) of Green Bull Terrier is put on the plate. It should come in contact with Honduras and Guadeloupe, should not go beyond the border of the plate and should have maximum radius.

Each of the following portions of the Green Bull Terrier must necessarily touch the Golden Honduras, the previous portion of the Green Bull Terrier and touch the edge of a plate, but should not go beyond the border.

To determine whether a stranger is worthy to touch the food, the Martians ask him to find the radius of the k\-th portion of the Green Bull Terrier knowing the radii of a plate and a portion of the Golden Honduras. And are you worthy?

Input

The first line contains integer t (1 ≤ t ≤ 104) — amount of testcases.

Each of the following t lines contain three positive integers: the radii of the plate and a portion of the Golden Honduras R and r (1 ≤ r < R ≤ 104) and the number k(1 ≤ k ≤ 104).

In the pretests 1 ≤ k ≤ 2.

Output

Print t lines — the radius of the k\-th portion of the Green Bull Terrier for each test. The absolute or relative error of the answer should not exceed 10 - 6.

Input

2
    4 3 1
    4 2 2

Output

0.9230769231
    0.6666666667

Note

Dish from the first sample looks like this:

![f6d94713d4ef48962591dede686b48cd_v_1504182941][]

Dish from the second sample looks like this:

![b15b8737a68429dd5dc6ddef87ec90a5_v_1504182941][]

题目题意:题目给我们一个大盘子半径为R（图黑圆）,一个黄饼半径r (图黄圆) ,常数k,问放上k个绿饼(图绿圆)最小的那个一个绿圆的半径.(其中粉圆是放上黄圆后，能放上的最大圆）。

题目分析:先解决粉圆的问题，放上黄圆后的最大圆，肯定是要满足黄，粉，黑，三圆圆心在一条直线上，即r2=(R-r)

接下来就是绿圆的放置问题了，我们先了解一下笛卡尔定理，下面是百度对笛卡尔定理的解释:

若平面上四个半径为r 1、r 2、r 3、r 4的圆两两相切于不同点，则其半径满足以下结论：（1）若四圆两两外切，则  ![5ab5c9ea15ce36d366262be933f33a87e850b1cd.jpg][] ；

（2）若半径为r 1、r 2、r 3的圆内切于半径为r 4的圆中，则  ![b3119313b07eca80e0b7d550982397dda04483d3.jpg][]

这里我们要利用第二个定理，设r4为黑圆，r1为黄圆,r2为粉圆,则放上去的第一个绿圆的半径r3，满足

![b3119313b07eca80e0b7d550982397dda04483d3.jpg][]

为计算方便，我们令k1=(1/r1) 同理

则原公式变为(k1+k2+k3-k4)^2=2\*(k1^2+k2^2+k3^2+k4^2)

我们展开变形:k3^2-2\*(k1+k2-k4)\*k3+2\*(k1^2+k2^2+k4^2)-(k1+k2-k4)^2=0

我们由根与系数的关系值x1+x2=-b/a=2\*(k1+k2-k4)  (其中x1与x2分别是与粉圆相切的左右俩个圆的半径的倒数)

因为黄 粉 黑三圆圆心共线即，为对称图形，那么求出的第一个绿圆的俩个半径一定相等，即k3=(k1+k2-k4)

我们知道了第一个绿圆的半径，怎么求第k个了,(脑补画面)

我们将第一个绿圆现在看成粉圆，来求出它左右俩边的圆的半径的倒数(其中右边的那个圆是真正的粉圆（上一层的粉圆),我们由根与系数的关系求出了左右俩边的俩个圆的半径的倒数和，现在减去以知道的真正粉圆的半径倒数(右边的圆)就等于左边的圆(就是下一个绿圆的半径倒数).

一直循环k次就可以了。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    
    int main()
    {
        int t;
        scanf("%d",&t);
        while (t--) {
            int r1,r2,r3,k;
            scanf("%d%d%d",&r1,&r2,&k);
            r3=r1-r2;
            double k1,k2,k3,k4,ans;
            k1=1.0/r1,k2=1.0/r2,k3=1.0/r3;
            k4=(k2+k3-k1);//第一个绿圆的半径倒数
            for (int i=1;i<=k;i++) {
                ans=1/k4;
                double k5=2*(k2+k4-k1)-k3;//下一个绿圆的半径倒数
                k3=k4;//然后将粉圆传到下一个绿圆
                k4=k5;
            }
            printf("%.10lf\n",ans);
        }
        return 0;
    }

。

[f6d94713d4ef48962591dede686b48cd_v_1504182941]: https://odzkskevi.qnssl.com/f6d94713d4ef48962591dede686b48cd?v=1504182941
[b15b8737a68429dd5dc6ddef87ec90a5_v_1504182941]: https://odzkskevi.qnssl.com/b15b8737a68429dd5dc6ddef87ec90a5?v=1504182941
[5ab5c9ea15ce36d366262be933f33a87e850b1cd.jpg]: https://gss3.bdstatic.com/-Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D135/sign=d038ff39fe03918fd3d139c9643c264b/5ab5c9ea15ce36d366262be933f33a87e850b1cd.jpg
[b3119313b07eca80e0b7d550982397dda04483d3.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D213/sign=e8ad96cd29a446237acaa263ab237246/b3119313b07eca80e0b7d550982397dda04483d3.jpg