快速集合

题目描述

数轴上有$nn$个人，他们要选一个地点集合。
第$ii$个人初始在位置$a_{i}a\_i$上，他的移速最大是$b_{i}b\_i$单位/秒，请问最少需要花费多少秒，这$nn$个人可以在某一个点集合。

对于$100\mathrm{\%}100\backslash \%$的数据，保证$1\le n\le 100000,1\le a_i,b_i\le 1000001\le n\le 100000,1\le a\_i,b\_i\le 100000$。

分析

二分答案

寻找最少时间$MM$满足这$nn$个人的可移动区间存在交集。

可移动区间是$[a_i-b_i\times M,a_i+b_i\times M][a\_i-b\_i\times M,a\_i+b\_i\times M]$

边界

最短时间即所有人都在一个点上，不用移动即时间为$00$
最长时间即两个人分别在两端，且移动速度最慢为$11$，时间为$5000050000$

AC代码

/*
有 n 个人，他们要选一个地点集合。第 i 个人初始在位置 ai 上，他的移速最大是 bi 单位/秒，
请问最少需要花费多少秒，这 n 个人可以在某一个点集合。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,a[maxn],b[maxn];
bool check(double x){
	double L=-1e10,R=1e10;
	for(int i=1;i<=n;i++){
		double l=a[i]-x*b[i];
		double r=a[i]+x*b[i];
		L=max(L,l);R=min(R,r);
	}
	if(L>R) return false;
	return true;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
	double l=0,r=5e4;
	for(int i=1;i<=100;i++){
		double mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid;
	}
	printf("%.10f",r);
}