时间限制: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
设抛物线上的点坐标为（xx,yy），可以知道让求min(sqrt((xx - x) ^ 2 + (yy - y) ^ 2)）
从l到r区间开始三分，分为mid1 = (l + r) / 2, mid2 = (mid + r) / 2 ，可以发现并不是严格三等份，然后check一下答案偏向哪里，把区间移过去即可
#include <bits/stdc++.h>
#include <time.h>
#define fi first
#define se secondusing namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-8;
typedef pair<int,bool> P;
const int maxn = 1e6;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
inline int cmp1(db a,db b){ return sign(a - b);} /// a > b return 1 , 否则 0 -1;
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
ll phi(ll x) { ll res = x; for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1); while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res;}
void ex_gcd(ll a, ll b, ll &x, ll &y){if (b == 0) { x = 1;y = 0;return; } else { ex_gcd(b, a%b, x, y); ll t = x; x = y; y = t - (a / b)*y; } return ; }
int fa[maxn];
int Find(int x) { if(x != fa[x]) return fa[x] = Find(fa[x]); return fa[x];}
double a,b,c,x,y;
double diss(double xx){double yy = a * xx * xx + b * xx + c;return hypot(xx - x,yy - y);
}
int main() {
// ios::sync_with_stdio(false);while(cin >> a >> b >> c >> x >> y){double l = -200,r = 200;while(cmp1(l,r) != 0){double mid1 = (l + r) / 2;double mid2 = (mid1 + r) / 2;double dis1 = diss(mid1);double dis2 = diss(mid2);if(dis1 < dis2){r = mid2;}else l = mid1;}double ans = diss(l);printf("%.3f\n",ans);
// cout << ans << endl;}cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}