BZOJ 2876 【NOI2012】 骑行川藏

题目链接：骑行川藏

　　听说这道题需要一些高数知识

　　于是膜了一发dalao的题解……然后就没了……

　　不要吐槽我的精度TAT……eps设太小了就TLE，大了就Wa……我二分的边界是对着数据卡的……

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define N 10010

#define eps 1e-12

using namespace std;

typedef long double llg;

int n;

llg E,s[N],k[N],v1[N],v[N],maxv[N];

void read(llg &x){

	double a;

	scanf("%lf",&a); x=a;

}

bool check(llg x){

	llg l,r,mid,now=0;

	for(int i=1;i<=n;i++){

		l=max(v1[i]+eps,(llg)0.0); r=maxv[i];

		while(r-l>=eps){

			mid=(r+l)*0.5;

			if(x*k[i]*mid*mid*(mid-v1[i])>=-0.5) l=mid;

			else r=mid;

		}

		v[i]=l; now+=k[i]*(l-v1[i])*(l-v1[i])*s[i];

	}

	return now<=E;

}

int main(){

	File("bicycling");

	scanf("%d",&n); read(E);

	for(int i=1;i<=n;i++){

		read(s[i]),read(k[i]),read(v1[i]);

		if(s[i]<=eps){i--,n--;continue;}

		maxv[i]=sqrt(E/k[i]/s[i])+v1[i];

	}

	llg l=-3,r=-eps,mid;

	while(r-l>=eps){

		mid=(r+l)*0.5;

		if(check(mid)) l=mid;

		else r=mid;

	}

	check(l); llg ans=0;

	for(int i=1;i<=n;i++) ans+=s[i]/v[i];

	printf("%.9lf",(double)ans);

	return 0;

}