记录编号	60956	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2012]骑行川藏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.278 s
提交时间	2013-06-01 19:24:15	内存使用	0.70 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
const int SIZEN=10001;
const double eps=1e-12;
const double INF=1e8;
int n;
double e;//体力值
double s[SIZEN]={0};//每段路程长度
double k[SIZEN]={0};//每段路程的风阻系数
double v0[SIZEN]={0};//每段路程的vi'
double ind[SIZEN]={0};//初始的导数
double inv[SIZEN]={0};//初始速度
double ind_min;
inline double sqr(double x){return x*x;}//平方
inline double cur(double x){return x*x*x;}//立方
double fa,fb,fd;//三次,二次,常数项
double f(double x){//三次函数值
	return fa*cur(x)+fb*sqr(x)+fd;
}
double df(double x){//三次函数的导数
	return 3*fa*sqr(x)+2*fb*x;
}
double slove(double x0){//从x0开始解方程f(x)=0,其中f(x)诸参数已确定
	double x1=x0;
	do{
		x0=x1;
		x1=x0-(f(x0)/df(x0));
	}while(fabs(x1-x0)>eps);
	return x1;
}
double mind;//导数的最小值
double nowe,nowt;
void single(int x){//对于确定的mind和第x段路,计算其应有的参数并用其累加nowe和nowt
	double v;
	if(ind[x]>mind){
		nowe+=k[x]*sqr(inv[x]-v0[x]);
		nowt+=s[x]/inv[x];
		return;
	}
	fa=2*k[x]*mind,fb=-2*k[x]*mind*v0[x],fd=1;
	v=slove(inv[x]);
	nowe+=s[x]*k[x]*sqr(v-v0[x]);
	nowt+=s[x]/v;
}
void calc(void){//对于给定的mind,计算nowe和nowt
	nowe=nowt=0;
	int i;
	for(i=1;i<=n;i++) single(i);
}
void work(void){//二分mind
	double left,right;
	left=-INF,right=-eps;
	double mid;
	while(right-left>eps){
		mid=(left+right)/2.0;
		mind=mid;
		calc();
		if(nowe>e) right=mid;
		else left=mid;
	}
	calc();
	cout<<setiosflags(ios::fixed)<<setprecision(10)<<nowt<<endl;
}
void init(void){
	scanf("%d%lf",&n,&e);
	int i;
	ind_min=0;
	for(i=1;i<=n;i++){
		scanf("%lf%lf%lf",&s[i],&k[i],&v0[i]);
		inv[i]=v0[i]>0?v0[i]:eps;
		ind[i]=inv[i]==v0[i]||inv[i]==eps?-INF:-1/(2*k[i]*sqr(inv[i])*(inv[i]-v0[i]));
		ind_min=ind[i]<ind_min?ind[i]:ind_min;
	}
}
int main(){
	freopen("bicycling.in","r",stdin);
	freopen("bicycling.out","w",stdout);
	init();
	work();
	return 0;
}