abc_f 求助
  • 板块灌水区
  • 楼主Tomwsc
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/12/21 22:16
  • 上次更新2024/12/22 10:46:01
查看原帖
abc_f 求助
1418967
Tomwsc楼主2024/12/21 22:16

二分和计算两点斜率打挂了,求调。 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;
}
2024/12/21 22:16
加载中...