题目link：https://loj.ac/problem/10013
经典的三分裸题。
三分主要是用来求一个满足单峰性的函数的最大/最小值的一种算法，其原理和二分基本一样。假设求最小值，首先把选择区域分为三段，然后比较这两个三等分点的函数值谁更小一些，大的那一边就不要了（如果大的是靠左的，那就连着左边不要了，靠右同理），容易证明这样做是正确的，然后像二分那样递归下去就可以得解。
这道题是裸题思路就没什么好说的了。
1 #include <bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 using namespace std; 4 int T, n, a[100010], b[100010], c[100010]; 5 double cal(double x) 6 { 7 double ans = -INF; 8 for(int i = 1; i <= n; ++i) ans = max(ans, a[i] * x * x + b[i] * x + c[i]); 9 return ans; 10 } 11 double half() 12 { 13 double ans = 0, l = 0, r = 1000; 14 for(int o = 1; o <= 100; ++o) 15 { 16 double mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3; 17 if(cal(mid1) < cal(mid2)) ans = mid1, r = mid2; else l = mid1; 18 } 19 return cal(ans); 20 } 21 int main() 22 { 23 scanf("%d", &T); 24 while(T--) 25 { 26 scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d %d %d", &a[i], &b[i], &c[i]); 27 printf("%.4lf\n", half()); 28 } 29 return 0; 30 }
原文：https://www.cnblogs.com/qqq1112/p/13922198.html