二分和计算两点斜率打挂了,求调。 orz
代码如下:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 10;
int n;
struct Node {
long double x , y;
};
Node a[MAXN];
inline bool check(long double x) {
long double k = - 1e18;
for(register int i = 1;i <= n;i ++) {
long double l = (long double)(a[i].y - x) / a[i].x;
if(l <= k)
return false;
k = max(k , l);
}
return true;
}
signed main() {
long double l = 0 , r = 0;
cin >> n;
for(register int i = 1;i <= n;i ++) {
cin >> a[i].x >> a[i].y;
r = max(r , a[i].y);
}
if(check(0.00000000))
cout << -1;
else {
while(r - l >= 0.00000000001) {
long double mid = (l + r) / 2;
if(check(mid))
r = mid;
else
l = mid;
}
cout << fixed << setprecision(15) << l;
}
return 0;
}