二分答案超时求助
查看原帖
二分答案超时求助
285617
黑影洞人楼主2022/8/12 11:43
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 1919810
#define inf 2147483647
using namespace std;
int n;
double x[N];
struct node{
	double x,v;
	bool operator<(const node &c)const{return x<c.x;}
}a[N];
bool abche(double a,double b){
	return (a>0&&b<0)||(b>0&&a<0);
}
bool check(double mid){
	//printf("mid:%lf",mid);puts("--fi--");
	double ri=-1e30,li=0;
	for(int i=1;i<=n;i++){
		if(a[i].v>0)ri=max(ri,a[i].x+a[i].v*mid);
		else{
			li=a[i].x+a[i].v*mid; 
			if(ri>li)return 1;
		}
	}
	//puts("--fi--");
	//for(int i=1;i<n;i++)if(x[i]>=x[i+1]&&abche(a[i].v,a[i+1].v))return 1;
	//puts("false");
	//puts("$$check$$");
	return 0;
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].v);
	sort(a+1,a+n+1);
	bool flg=1;
	for(int i=1;i<=n;i++)
		if(a[i].v>0){
			for(int j=i+1;j<=n;j++)if(a[j].v<0){flg=0;break;}
			break;
		}
	if(flg)return puts("-1"),0;
	double l=0,r=1e9;
	int tot=0;
	while(fabs(r-l)>1e-10){
		tot++;
		//if(tot>1145)return puts("-1"),0;
		double mid=(l+r)/2;
		//printf("%.16lf %.16lf %.16lf\n",l,mid,r);
		//if(l==r)break;
		if(check(mid))r=mid;
		else l=mid; 
	}
	if(r==0)puts("-1");
	else printf("%.16lf",r);
	return 0;
}



2022/8/12 11:43
加载中...