CF24E Berland collider 题解

分析

将时间二分，对于每一个二分得到的时间，从左至右搜每一个子弹，如果是从左往右飞的，就计算出它在这个时刻的坐标，取所有现坐标的最大值；如果是从右往左飞的，就看目前有没有从左往右飞的子弹此前能和它相遇，也就是比较它的现坐标是否小于从左往右飞子弹的现坐标最大值。如果能相遇，就更新答案，否则继续二分。

代码

#include 
using namespace std;
const int MAXN=5e5+7;
inline void qread(){}template
inline void qread(T1 &a,T2&... b)
{
	register T1 x=0;register bool f=false;char ch=getchar();
	while(ch<'0') f|=(ch=='-'),ch=getchar();
	while(ch>='0') x=(x*10)+(ch^48),ch=getchar();
	x=(f?-x:x);a=x;qread(b...);
}
templateinline T qmax(const T &x,const T &y){return x>y?x:y;}
templateinline T qmin(const T &x,const T &y){return x0) mx=qmax(mx,a[i].x+a[i].v*mid);
		else
		{
			long double t=(a[i].x+a[i].v*mid);
			if(t=1e-10)
	{
		long double mid=(l+r)/2;
		if(check(mid)) ans=r=mid;
		else l=mid;
	}
	if(r==1e9+7) ans=-1;
	printf("%.10Lf\n",ans);
	return 0;
}