首页 > 代码库 > ACdream1034:the cover circle

ACdream1034:the cover circle

2024-07-06 00:07:35   225人阅读

Problem Description

用半径相等的两个圆覆盖一个w*h的矩形，要求两圆不相交且必须在矩形内。求覆盖面积最大时两圆半径。

Input

输入包含多组数据，EOF结束。

每组数据包含一行，分别是两个实数w和h代表矩形的长和宽。

0<w,h<10000

Output

每组数据输出一行表示圆的半径，小数点后保留三位。

Sample Input

2.000 1.000

Sample Output

0.500


思路：我们可以以矩形的一个顶点为原点坐标（0,0），那么其斜对角的坐标为（w,h）

而这两个圆可以看做是从这两个点开始吹的气球

那么我们可以二分其半径


#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define exp 1e-8

int main()
{
    double h,w,l,r,mid,x,y,mid2;
    while(~scanf("%lf%lf",&w,&h))
    {
        if(w<h)
            swap(w,h);
        l = 0,r = h/2;
        while(r-l>exp)
        {
            mid = (l+r)/2;//原点出发的圆的半径
            x = w-mid;//求出（w,h）出发的圆的圆心坐标
            y = h-mid;
            mid2 = sqrt((mid-x)*(mid-x)+(mid-y)*(mid-y))/2.0;//两圆心的距离除以2
            if(mid>mid2)
                r = mid;
            else
                l = mid;
        }
        printf("%.3f\n",l);
    }

    return 0;
}



联系
我们