来源与分析：
http://chenjianneng3.blog.163.com/blog/static/128345126201033101044920/因为是求极值，所以要注意所求的数据范围，特别是最大，最小可能值。
2010 成都赛区的
Error Curves 就是典型的三分：
附上我的程序：
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10010;
const double eps = 1e-8;
double a[maxn],b[maxn],c[maxn];
int n;
double cal(double x)
{
double s = -1e100,tmp;//注意s的要尽量小
for (int i = 1; i <= n; i++)
{
tmp = a[i]*x*x + b[i]*x + c[i];
s = max(tmp,s);
}
return s;
}
void solve()
{
double left = 0.0, right = 1000.0;
double mid, midmid;
double mid_v, midmid_v;
while (left + eps < right)
{
mid = (left + right) / 2;
midmid = (mid + right) / 2;
mid_v = cal(mid);
midmid_v = cal(midmid);
if (mid_v < midmid_v)
right = midmid;
else left = mid;
}
printf("%.4lf\n",cal((left+right)/2));
}
int main()
{
int t,i,j;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (i = 1; i <= n; i++)
scanf("%lf %lf %lf",&a[i],&b[i],&c[i]);
solve();
}
return 0;
}
某某程序：
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 10086;
double a[MAXN], b[MAXN], c[MAXN];
int main() {
int re, n;
double l, r, m1, m2, y1, y2;
scanf("%d", &re);
for (int ri = 1; ri <= re; ++ri) {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%lf%lf%lf", &a[i], &b[i], &c[i]);
}
l = 0;
r = 1000;
while (r - l > 1e-8) {
m1 = (l * 2 + r) / 3;
m2 = (l + r * 2) / 3;
y1 = y2 = -1e100;
for (int i = 0; i < n; ++i) {
y1 = max(y1, (a[i] * m1 + b[i]) * m1 + c[i]);
y2 = max(y2, (a[i] * m2 + b[i]) * m2 + c[i]);
}
if (y1 < y2) {
r = m2;
} else {
l = m1;
}
}
l = (l + r) / 2;
r = -1e100;
for (int i = 0; i < n; ++i) {
r = max(r, (a[i] * l + b[i]) * l + c[i]);
}
printf("%.4lf\n", r);
}
return 0;
}
三分法小结：只要解在一点范围内满足凸函数性质就行，通俗点说就是两边夹，从两边不断逼近。
模版化：
double Cal(Type a)
{
/* 根据题目的意思计算 */
}
void Solve(void)
{
double Left, Right;
double mid, midmid;
double mid_value, midmid_value;
Left = MIN; Right = MAX;
while (Left + EPS < Right)
{
mid = (Left + Right) / 2;
midmid = (mid + Right) / 2;
mid_value = Cal(mid);
midmid_value = Cal(midmid);
// 假设求解最大极值.
if (mid_value >= midmid_value) Right = midmid;
else Left = mid;
}
}
poj3301cpp代码：
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double PI = acos(-1.0);
const double eps = 1e-8;
const double maxn = 1000;
int n;
double x[35],y[35];
double cal(double a)
{
double bx ,by ,sx,sy;
bx = by = -maxn ,sx = sy = maxn;
double tx,ty;
for (int i = 1; i <= n; i++)
{
//tx，ty为坐标变换后的坐标，具体怎么推得忘了？？？？
tx = x[i] * cos(a) - y[i] * sin(a);
ty = y[i] * cos(a) + x[i] * sin(a);
bx = max(tx,bx);
sx = min(tx,sx);
by = max(ty,by);
sy = min(ty,sy);
}
return max(bx - sx , by - sy);
}
int main()
{
int t,i,j;
double lf,rt;
double m1,m2;
double m1_v,m2_v;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (i = 1; i <= n; i++)
scanf("%lf %lf",&x[i],&y[i]);
lf = 0.0; rt = PI/2;
while (lf + eps < rt)
{
m1 = (lf + rt) / 2;
m2 = (m1 + rt) / 2;
m1_v = cal(m1);
m2_v = cal(m2);
if (m1_v <= m2_v)
rt = m2;
else lf = m1;
}
double len = cal(lf);
printf("%.2lf\n",len*len);
}
return 0;
}