http://acm.bupt.edu.cn/dahao/wiki/index.php?title=6.8_%E8%BF%AD%E4%BB%A3%E9%80%BC%E8%BF%91&oldid=355
Compared to wildleopard's wealthiness, his brother mildleopard is rather poor. His house is narrow and he has only one light bulb in his house. Every night,
he is wandering in his incommodious house, thinking of how to earn more money. One day, he found that the length of his shadow was changing from time to time while walking between the light bulb and the wall of his house. A sudden thought ran through his mind
and he wanted to know the maximum length of his shadow.
Each test case contains three real numbers H, h and D in one line. H is the height of the light bulb while h is the height of mildleopard. D is distance between the light bulb and the wall. All numbers are in range from 10^(-3) to 10^2, both inclusive, and
H - h >= 10^(-3).
2 2 1 0.5 2 0.5 3
1.000 0.750
如果用公式解,如图所示
三分
二分法作为分治中最常见的方法,适用于单调函数,逼近求解某点的值。但当函数是凸性函数时,二分法就无法适用,这时三分法就可以大显身手。如下凸函数:
类似二分的定义left和right
mid1 = (left + right) / 2 mid2 = (mid2 + right) / 2 如果mid1靠近极值点, left = mid1 如果mid2靠近极值点, right = mid2
java版三分ac代码:
//三分 import java.util.Scanner; public class Main { static double H,h,d; public static double result(double x) { double t= H+d-(H-h)*d/x-x; return t; } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int cases=scanner.nextInt(); while(cases--!=0) { H=scanner.nextDouble(); h=scanner.nextDouble(); d=scanner.nextDouble(); double left,right; double mid ,midmid; double midresult = 0,midmidresult = 0; left=(H-h)*d/H;right=d; while(left+(1e-9)<right) { mid=(left+right)/2; midmid=(mid+right)/2; midresult=result(mid); midmidresult=result(midmid); if(midresult>=midmidresult) right=midmid; else { left=mid; } } System.out.printf("%.3f\n",midmidresult); } } }
c/c++版的公式计算ac代码:
#include<stdio.h> #include<math.h> int main() { double H,D,h,t,result1,result2; int test; scanf("%d",&test); while(test--) { scanf("%lf%lf%lf",&H,&h,&D); t=sqrt(D*(H-h)); result1=D*h/H; if(D>=t && t>=D-D*h/H) result2=H+D-2*t; else result2=h; printf("%.3f\n",result1>result2?result1:result2); } return 0; }
java版公式代码,但是没有ac,zoj上ac,但是nyoj上ac不了
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int cases=scanner.nextInt(); while(cases--!=0) { double H,h,d; H=scanner.nextDouble(); h=scanner.nextDouble(); d=scanner.nextDouble(); double temp=Math.sqrt(d*(H-h)); double result1=d*h/H; double result2; if(d>=temp&&temp>=d-d*h/H) result2=H+d-2*temp; else { result2=h; } System.out.printf("%.3f\n",(result1>result2?result1:result2)); } } }