Hihocoder-1142 : 三分·三分求极值
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
这一次我们就简单一点了,题目在此:
在直角坐标系中有一条抛物线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
题解:
简单的凸函数求解极值的方法,按照要求实现就可以了。
准备公式:
(1), 点到直线的距离公式:d=│AXo+BYo+C│ / √(A²+B²)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std; double a, b, c, x, y;
double function(double x0){
return sqrt((x0-x)*(x0-x) + (a*x0*x0 + b*x0 + c - y)*(a*x0*x0 + b*x0 + c - y));
} int main(){
freopen("in.txt", "r", stdin); scanf("%lf %lf %lf %lf %lf", &a, &b, &c, &x, &y); if( fabs(a) < 0.000001){
if(fabs(b) < 0.000001){
printf("%.3lf\n", fabs(y-c) );
}else{
printf("%.3lf\n", (b*x - y + c)/(sqrt(b*b + 1)) );
}
} else {
double lmin, rmin, left = -100000.0, right = 100000.0;
while( right-left > 0.0001) {
lmin = function( left + (right-left)/3.0 );
rmin = function( right - (right-left)/3.0 );
if(lmin > rmin){
left = left + (right-left)/3.0;
} else {
right = right - (right-left)/3.0;
}
}
printf("%.3lf\n", lmin);
}
return 0;
}