TOJ 72 Happiness Function ( 三分搜 )
http://sprout.tw/oj/pro/72/
一個三分搜模板。每次總是縮小至少三分之一的搜索範圍,慢慢走往凹點。
#include <cstdio> int n; double a[10], b[10], c[10]; double S(double t){ double mx = 0; for(int i = 0; i < n; ++i) if(a[i]*(t-b[i])*(t-b[i])+c[i] > mx) mx = a[i]*(t-b[i])*(t-b[i])+c[i]; return mx; } int main(){ int T; for(scanf("%d", &T); T; --T){ scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%lf %lf %lf", &a[i], &b[i], &c[i]); double w = 0, x, y, z = 300; for(int i = 0; i < 100; ++i){ x = (z-w)/3.0 + w; y = z - (z-w)/3.0; if(S(w) < S(x) && S(x) < S(y) && S(y) < S(z)) z = y; else if(S(w) > S(x) && S(x) < S(y) && S(y) < S(z)) z = y; else if(S(w) > S(x) && S(x) > S(y) && S(y) < S(z)) w = x; else if(S(w) > S(x) && S(x) > S(y) && S(y) > S(z)) w = x; else w = x, z = y; } printf("%.5lf\n", S(w)); } return 0; }