Gym - 100796I Shell Game 计算几何

最新推荐文章于 2020-09-19 13:54:54 发布

陈年风褛

最新推荐文章于 2020-09-19 13:54:54 发布

阅读量527

点赞数 1

分类专栏： GYM

本文链接：https://blog.csdn.net/lmhacm/article/details/61622607

版权

GYM 专栏收录该内容

2 篇文章

订阅专栏

博客讲述了ACM ICPC Baltic Selection Contest中的一道题——Shell Game，涉及到计算几何问题。玩家需猜测球在三个杯子中的位置，但球会因粘合剂而留在被翻转的杯子里。问题转化为求解能放入圆台形杯子的最大球体半径。通过相似三角形原理，计算得出最大半径的公式，并提供了解题代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Bob has discovered a new quality in himself — he likes to trick people a lot! In particular, Bob wants to try his tricking skills in the shell game.

The shell game involves three identical cups and a single ball. In the beginning the host (that's Bob!) puts the cups upside down and places the ball inside one of the cups. Then he shuffles the cups and the player has to guess where the ball is. The host then lifts that cup, revealing whether the ball was inside or not. The player wins if he makes a correct guess, otherwise the host wins.

The form of each cup is a sliced cone. Formally, the base of the cup is a circle with radiusr, and the opening of the cup is a circle with radiusR. The height of the cup is equal to h. A ball for the shell game is simply a sphere.

$\text{[math]}$

What the player is not going to know is that Bob smeared the inner surface of each cup with glue, resulting in the cup holding the ball when Bob lifts it up — so the player will never win! However, the ball will stick only if it touches the inner surface of a cup. For this reason Bob wants to get the largest possible ball that fits inside the cup when the cup is placed upside down on the table.

Bob has already found three identical cups in his grandmother's locker — now he only has to buy a ball of the required size so that he may start playing the shell game. Help Bob and calculate the largest size of such a ball!

Input

The first line contains three space-separated integers r, R and h, the radii of the base and the opening, and the height of the cup (1 ≤ r < R ≤ 10⁴,1 ≤ h ≤ 10⁴).

Output

Output a single number — the radius of the largest ball that can fit in the cup. Your answer will be considered correct if its relative or absolute error doesn't exceed10^- 6.

Examples

Input

3 4 8

Output

3.531128874149

这题队里分配本来是我的题，结果最后算了半天没做出来......然后队友给A了，而且我还当了个罪人→_→这是后话，一会再说。

题目意思很好理解，一个.....额，这叫什么，圆台？在这个圆台里面放一个球体，问能放入的最大球体的半径是多少。因为要放入的是最大的，所以圆心一定在圆台的中间，所以这个立体几何的问题就可以转换为平面几何的问题，然后，弄了个式子化简不出来GG了，具体推的过程不说了，反正也是错的→_→

之后队友过来帮我解题→_→唉，数学已废。首先把这个图形还原成一个椎体，然后还是化为平面几何做。

这样上面的小直角三角形和大的直角三角形就构成了相似三角形，要求的球体半径就是a，通过相似三角形，可以得到H/(H+h)=r/R，化简得到H=(h/(R-r)+h)，而l=sqrt(H^2+R^2)，之后再通过式子HR-aR=al便可以化简得出a的式子，恩不打出来了，好麻烦→_→

结果最后我按着队友推出来的式子写了个程序，不知是哪打错了，结果不对。然后大神队友拿出了垂心重心内心欧拉定理等等公式重新推，我反正是听的一脸懵逼了= =干脆甩给队友去做另一个题了，最后队友A了，用的是他之前的式子......好吧也不知道我第一遍怎么打错的。

下面队友的AC代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<string>
#include <set>
using namespace std;
#define ll long long
#define mem(a) memset(a,0,sizeof(a))
const int eps=1e-8;
const int maxn=30010;//须填写
const int inf=0x3f3f3f3f;
int main()
{
    double r,R,h;
    while(scanf("%lf%lf%lf",&r,&R,&h)!=EOF)
    {
        double H=(r*h)/(R-r)+h;
        double r1=(H*H+R*R)/(2*H);
        double l=sqrt(H*H+R*R);
        double a=(R*H)/(l+R);
        if(a*2<h)
            printf("%.12f\n",a);
        else printf("%f\n",h/2);
    }
    return 0;
}