求调ABC F
  • 板块题目总版
  • 楼主_Fancy_
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/12/21 21:43
  • 上次更新2024/12/22 09:52:40
查看原帖
求调ABC F
729386
_Fancy_楼主2024/12/21 21:43

思路是二分最小的无法全部看见的点,用斜率判断,AC * 8+WA * 19

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const double eps = 1e-10;
int n;
struct node {
	int x, h;
} a[N];
bool check(double h0) {
	double maxx = -1e18;
	for(int i = 1; i <= n; i++) {
		if(((double)a[i].h - h0) / a[i].x <= maxx) return false;
		maxx = max(maxx, ((double)a[i].h - h0) / a[i].x);
	}
	return true;
}
int main() {
	scanf("%d", &n);
	double l = 0, r = 0;
	for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].h), r = max(r, (double)a[i].h);
	if(check(0.00)) {
		cout << -1;
		return 0;
	}
	while(r - l >= eps) {
		double mid = (l + r) / 2;
		if(check(mid)) r = mid;
		else l = mid;
	}
	printf("%.15f", r);
	return 0;
}
2024/12/21 21:43
加载中...