首页 > 代码库 > ZOJ 3203 Light Bulb 三分

ZOJ 3203 Light Bulb 三分

2024-07-10 03:20:30   224人阅读

最简单的三分题，期末考完先做一道练练手

就是这么一个图，告诉你H h D，问你L最长是多少，假设人到灯的距离是X，那么容易得到

L = H-D/x*(H-h)+D-x,求个导很容易发现是一个关于x 的凸性函数，就可以三分啦

要注意的是三分的时候的精度eps，这题要求得是1e-9才能A，1e-8都WA，真是囧

#include <cstdio>#include <sstream>#include <fstream>#include <cstring>#include <iostream>#include <algorithm>#include <map>#include <cctype>#include <ctime>#include <set>#include <climits>#include <vector>#include <queue>#include <stack>#include <cstdlib>#include <cmath>#include <string>#include <list>#define INPUT_FILE "in.txt"#define OUTPUT_FILE "out.txt"using namespace std;typedef long long LL;const int INF = INT_MAX / 2;const double eps = 1e-9;void setfile() {    freopen(INPUT_FILE,"r",stdin);    freopen(OUTPUT_FILE,"w",stdout);}double f(double H,double h,double D,double x) {    return H - D / x * (H - h) + D - x;}//三分搜索double tsearch(double H,double h,double D) {    double l = D * (H - h) / H,r = D,mid,midr;    while(fabs(l - r) > eps) {        mid = (l + r) / 2;        midr = (mid + r) / 2;        if(f(H,h,D,mid) > f(H,h,D,midr)) {            r = midr;        } else l = mid;    }    return f(H,h,D,l);}int main() {    int T; scanf("%d",&T);    double H,h,D;    for(int kase = 1;kase <= T;kase++) {        scanf("%lf%lf%lf",&H,&h,&D);        printf("%.3f\n",tsearch(H,h,D));    }    return 0;}


联系
我们