hdu 6158 The Designer && 计蒜客 Finding the Radius for an Inserted Circle 笛卡尔定理应用+韦达定理

80 阅读 0 评论 53 点赞

我是靠谱客的博主缓慢宝贝，最近开发中收集的这篇文章主要介绍hdu 6158 The Designer && 计蒜客 Finding the Radius for an Inserted Circle 笛卡尔定理应用+韦达定理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

HDU6158
题意 :
这里写图片描述
有两个圆相内切，在两个圆之间添加n个圆使得其与相邻的圆都相切，添加的顺序如图，求n个圆的总面积。
思路:

这是一道典型的笛卡尔定理应用,我们先来介绍一下笛卡尔定理

笛卡尔定理

定义：

若平面上四个半径为r1、r2、r3、r4的圆两两相切于不同点，则其半径满足以下结论：
（1）若四圆两两外切，则 $(sum_{i=1}^{4}frac{1}{r_i})^2 = 2*sum_{i=1}^{4}frac{1}{r_i^2}$
（2）若半径为r1、r2、r3的圆内切于半径为r4的圆中，则
$(frac{1}{r_1}+frac{1}{r_2}+frac{1}{r_3}-frac{1}{r_4})^2 = 2*sum_{i=1}^{4}frac{1}{r_i^2}$

韦达定理
$x_1+x_2 = -frac{b}{a}$
$x_1*x_2 = frac{c}{a}$

在该题中我们已知四个相切圆中三个的半径，即r1,r2,r1−r2，因为圆的曲率 $k=frac{1}{r}$ ，那么我们根据题意可以将笛卡尔定理转化为 $(k1+k2+k3+k4)2=2∗(k_1^2+k_2^2+k_3^2+k_4^2)$ ，其中
$k1 =−frac{1} {r_1}$ ， $k2=frac{1}{r_2}$ ， $k3=frac{1}{r_3}$ ，k4为未知圆r4的曲率，
化简可得：
$k_4^2−2∗(k1+k2+k3)∗k4−(k1+k2+k3)^2+2*(k_1^2+k_2^2+k_3^2)=0，$
根据韦达定理，可得x1+x2=2∗(k1+k2+k3)。这样k1,k2,k3我们都知道了.就可以递推求出其他解了.
这里写图片描述
根据上面的图片,我们一直k1,k2,k3，第一次韦达定理得出的是 2*K4,得到了k4之后我们第二次韦达定理得出的是k4直接相切的两个圆,分别是1和5,因为1已知进而可以得出5,一次类推.

然后发现这样做仍然是T的,可以想到当精度小到一定程度的时候对结果没影响了,我们直接结束就好了.

#include<bits/stdc++.h>
#define PI  acos(-1.0)
typedef long long ll;
const double exps = 1e-13;

int main()
{
    int _;
    std:: cin>>_;
    double r1,r2,ans,k1,k2,k3,k4,k5;
    int n;
    while(_--)
    {
        std:: cin>>r1>>r2;
        std:: cin>>n;
        if(r1 < r2) std:: swap(r1,r2);
        k1 = -1.0/r1,k2 = 1.0/r2,k3 = 1.0/(r1-r2);
        ans = (r1-r2)*(r1-r2);
        n--;
        k4 = (k1+k2+k3);
        for(int i = 1;i <= n;++i)
        {
            double r =  1.0/k4;
            if(r*r < exps) break;
            ans += r*r;
            if(i + 1 <= n) ans += r*r,i++;
            k5 = 2*(k1 + k2 + k4) - k3;
            k3 = k4;
            k4 = k5;
        }
        printf("%.5fn",ans*PI);
    }
    return 0;
}

Finding the Radius for an Inserted Circle

题意：
给你三个半径为R的圆,两两相切,他们相切的中间部分往里面继续插圆,问你插入的第k个相切的圆半径是多少？输出整数部分. k<=10；

思路: 这个题目也是韦达定理+笛卡尔定理.观察到每四个圆都是两两相切,且切于不同点,所以我们可以用笛卡尔定理的结论来计算第4个圆的半径是多少.这个过程需要解个一元二次方程组,用韦达定理来解.然后每次递推,结论同上.

#include<bits/stdc++.h>
#define PI  acos(-1.0)
typedef long long ll;
const double exps = 1e-13;

int main()
{
    int _;
    while(std:: cin>>_)
    {
        if(_ == -1) break;
    double r,k1,k2,k3,ans;
    int k;
    std:: cin>>r; 

    while(_--)
    {
        std::cin>>k;
        k1 = 1/r,k2=1/r,k3=1/r;
        for(int i = 1;i <= k;++i)
        {
            double b = -2*(k1+k2+k3);
            double c = 2*(k1*k1+k2*k2+k3*k3)-(k1+k2+k3)*(k1+k2+k3);
            double data = b*b - 4*c;
            double x = (-b+ sqrt(data))/2;
            ans = 1/x;
            k3 = x;
        }
        ans = floor(ans);
        std:: cout<<k<<' '<<ans<<std:: endl;
    }

    }
    return 0;
}