# 洛谷2179 [noi2012]骑行川藏

## 拉格朗日乘法入门题

Posted by yjjr's blog on April 3, 2018 1 minutes to read

# 题目

## 输入输出样例

### 输入样例#1

3 10000
10000 10 5
20000 15 8
50000 5 6


### 输出样例#1

12531.34496464


## 说明

### 数据规模与约定

$s_i\in(0,10^5],k_i\in(0,15],v_i'\in(-100,100)$ .

# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
#define eps 1e-12
#define inf 1e9
const int maxn=5e4+6;
int n;
double e,s[maxn],k[maxn],v[maxn],x[maxn];
double calc(double ld){
double tot=0;
rep(i,1,n){
double l=max(0.0,v[i]),r=inf;
while(r-l>eps){
double mid=(l+r)/2;
if(2*ld*k[i]*mid*mid*(mid-v[i])>1)r=mid;
else l=mid;
}
x[i]=l;
tot+=k[i]*s[i]*(x[i]-v[i])*(x[i]-v[i]);
}
}
int main()
{
scanf("%d%lf",&n,&e);
rep(i,1,n)scanf("%lf%lf%lf",&s[i],&k[i],&v[i]);
double l=0,r=inf;
while(r-l>eps){
double mid=(l+r)/2;
if(calc(mid)>=e)l=mid;else r=mid;
}
double ans=0;
rep(i,1,n)ans+=s[i]/x[i];
printf("%.10lf\n",ans);
return 0;
}