首页 > 代码库 > ZOJ Problem Set - 3203 Light Bulb 【三分法】
ZOJ Problem Set - 3203 Light Bulb 【三分法】
题目:ZOJ Problem Set - 3203 Light Bulb
题意:
如图,有个人在地上走,然后他的影子可以投影到墙上或者地上,问影子最长是多少?
分析:
我们知道,三分法是解决一个凹或凸函数的极大极小值,发现这个影子从刚好投影到右下角开始便是一个凸函数,他的影子长度是先递增后递减的,所以可以用三分法。
三分法的原理:
AC代码:
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <map> #include <string> #include <iostream> using namespace std; #define Del(a,b) memset(a,b,sizeof(a)) typedef long long LL; double H,h,d; double solve(double x) { return d - x + H - d*(H-h)/x; //地上+墙上 } //三分法 double Yougth(double l,double r) { while(l+1e-10<r) { double mid = (l + r)/2; double midmid = (mid + r)/2; if(solve(mid) - solve(midmid)<0) l = mid; else r = midmid; } return l; } int main() { //freopen("Input.txt","r",stdin); int T; scanf("%d",&T); while(T--) { scanf("%lf%lf%lf",&H,&h,&d); double cs = Yougth(d - d*h/H,d); printf("%.3lf\n",solve(cs)); } return 0; }
ZOJ Problem Set - 3203 Light Bulb 【三分法】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。