题意与分析
题意是这样的,问你把一个长方形从一个L型街道的一端移动到另一端,固定了该长方形的长,求他的最大宽。
这种问题我是第一次独立解决(以前都是抱队友大腿QAQ),现在没法子只好自己硬着头皮做,看了题解。
不失一般性,保证\(a\le b\)。那么l要么比两个小,要么在一个中间,要么比他们都大。比两个小,那宽是最大值,也就是长了;在两个中间,那么宽直接取a就可以了(因为你要进去,如果a比b小你取大了也白给)。
最有意思的是第三种情况。我插一幅图说明一下:
宽度是一定的,问题就在于我们的\(l\)。把\(l\)像示意图那样靠在最左边,那么我们要求的就是\((b,a)\)到这条直线的距离的最大值,它是一个关于斜率,也就是底下横坐标\(x_0\)的函数。如果你数学能力比较强悍的话,可以直接试试解这个方程看看。问题在于我们是竞赛,没那么多时间,可以这么考虑:这个直线的摆动是对称的,因此如果有最大值,一定是在中间的——也就是经历一个增加到最大再减小的过程。这样一来就可以用三分算法来解决问题了。注意一下不存在的情况(如果最后算出来的结果是负数或者很小这种)。
这正好是我第一次写三分算法,很有价值的一题。
代码
/*
* ACM Code => cf99e.java
* Written by Sam X
* Date: 三月, 20, 2019
* Time: 14:25
*/
import java.util.*;
import java.math.*;
public class cf99e
{
static double a,b,l;
static final double eps=1e-9;
static final int sgn(double x)
{
if(Math.abs(x)<eps) return 0;
else if(x>eps) return 1;
else return -1;
}
static final double calc(double x)
{
return (Math.sqrt(l*l-x*x)*(b-x)+x*a)/l;
}
static void ternarySearch(double l, double r)
{
double midl, midr;
while(l+eps<r)
{
midl=l+(r-l)/3;
midr=r-(r-l)/3;
//System.out.println(mid+" "+midmid);
//System.out.println(calc(mid)+" "+calc(midmid));
if(Math.abs(calc(midl))<Math.abs(calc(midr))) // ask for maximum
{
r=midr;
}
else l=midl;
}
if(sgn(calc(l))<1)
System.out.println("My poor head =(");
else System.out.println(calc(l));
}
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
a=cin.nextDouble();
b=cin.nextDouble();
l=cin.nextDouble();
if(a-b>eps)
{
double t=a;
a=b;
b=t;
}
double minab = Math.min(a,b),
maxab = Math.max(a,b);
if(sgn(l-minab)<1) System.out.printf("%.7f\n", l);
else if(sgn(minab-l)<1 && sgn(l-maxab)<1) System.out.printf("%.7f\n", a);
else
{
ternarySearch(0, l);
}
cin.close();
}
}