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

ACdream1034:the cover circle

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;
}