hihocoder 1142 : 三分·三分求极值 三分

缘起

经常看到巨佬的博客上有”三分”的tag. 起初以为是搞笑, 后来才知道真有三分的算法. 遂本小白来学习.

hihocoder 1142 : 三分·三分求极值

分析

1
2
3
4
5
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
这一次我们就简单一点了，题目在此：
1
2
3
4
5
6
7
8
9
10
11
在直角坐标系中有一条抛物线y=ax^2+bx+c和一个点P(x,y)，求点P到抛物线的最短距离d。
输入
第1行：5个整数a,b,c,x,y。前三个数构成抛物线的参数，后两个数x,y表示P点坐标。-200≤a,b,c,x,y≤200

输出
第1行：1个实数d，保留3位小数(四舍五入)

样例输入
2 8 2 -2 6
样例输出
2.437

二分法大家都是极为熟悉的. 板子都有了. 二分法的前提是答案具备某种单调性——x可以, 则比x大（小）的更可以. 这样才能使用二分法. 但是对于本题, 其实完全可以使用数学手段——令(x0, f(x0))为抛物线上的那个点, 它和(x,y)之间的距离就是最短距离. 则必然和切线垂直. 于是就有1个约束方程. 就可以求出x0了. 但是会涉及到比较多的分类讨论而且就不能实践着这里的三分法了.

那么什么是三分法呢? 以凸函数求极小值为例，一图胜千言

这种情况先减后增有极小，若lm比rm低（即lm对应的函数值 < rm函数值）则极小点（图中最低点）肯定在[ left, rm ] ，反之在[ lm, right ]，剩下就跟二分一样根据大小关系调整区间就行了。那lm和rm取值多少？一个不错的取值是lm为整个区间的1/3点，rm为2/3点，即
lmid = l + (r - l)/3;
rmid = r - (r - l)/3;
嗯~三分就这样完了。

如果是凹函数呢? 就像下图（本题就是求极小, 到抛物线距离函数是凸函数,用不到这种情况）

代码的处理语句反过来即可.

套用本算法很容易ac本题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//#include "stdafx.h"
#include <stdio.h>
//#define LOCAL
#define SQUARE(x) ((x)*(x))
#include <math.h>
const double eps = 1e-8;
int a,b,c,x,y;

inline double f(double x)
{
	return a*x*x+b*x+c;
}

inline double dis(double x1, double y1, double x2, double y2)
{
	return sqrt(SQUARE(x1-x2)+SQUARE(y1-y2));
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d%d%d%d", &a, &b, &c, &x, &y);
	double lo = -200, hi = 200, ans, lmid, rmid;
	while(hi>lo+eps)
	{
		lmid = lo+(hi-lo)/3, rmid = hi-(hi-lo)/3; // lmid是左三等分点, rmid是右三等分点, ans是答案的横坐标
		if (dis(lmid, f(lmid), x,y)+eps < dis(rmid, f(rmid), x, y)) // 答案在[lo, rmid]中
		{
			ans = rmid;
			hi = rmid;
		}
		else // 答案在 [lmid, hi]中
		{
			ans = lmid;
			lo = lmid; // 和二分不一样, 三分在else情形还是要等于一下的
		}
	}
	printf("%.3lf", dis(ans, f(ans), x, y));
	return 0;
}

ac情况

结果:Accepted