题意：
小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A纪念券（以下简称A券）和B纪念券（以下简称B券）。
每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。
每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。
我们记录第i天中A券和B券的价值分别为$A_{i}$和$B_{i}$（元/单位金券）。
为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。
比例交易法分为两个方面：
- 卖出金券：顾客提供一个$[0,100]$内的实数op作为卖出比例，其意义为：将$op \% $的A券和$op \% $的B券以当时的价值兑换为人民币；
- 买入金券：顾客支付IP元人民币，交易所将会兑换给用户总价值为IP的金券，并且，满足提供给顾客的A券和B券的比例在第i天恰好为$Rate_{i}$；
小Y是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来n天内的A券和B券的价值以及Rate。
他还希望能够计算出来，如果开始时拥有S元钱，那么n天后最多能够获得多少元钱。
$nleq 10^{5},答案leq 10^{9}$。
题解：
不太容易地发现，每天要么把所有券买了，要么花掉所有钱买券，不会出现留着钱过夜这种操作。（反证法可证）
那么记$F_i$表示第i天结束后最多能获得多少元钱，则有$F_i =max{F_{i-1},F_j imes frac{R_j A_i + B_i }{R_j A_j +B_j}}$。
记$x_i=frac{R_i F_i}{R_i A_i + B_i},y_i=frac{F_i}{R_i A_i + B_i}$，则$F_i = A_i x_j + B_i y_j$，符合斜率优化的形式。
但发现一个恐怖的事情：$x_j$不是单调的，所以不能线性维护凸壳。
此时可以$Splay$维护凸壳，也可以CDQ分治维护，本题我采用后一种做法：
将第一维按下标排序，对于每个区间$[l,r]$，我们只需要知道左边的凸壳对右边的贡献即可。
于是先计算出左边的答案，然后将左边按$x_{i}$排序并建立凸壳，右边的每个点在凸壳上二分更新答案即可。
注意$F_i$还要在$F_{i-1}$处更新，所以还需要单开一个F满足下标限制。
该做法复杂度为$O(nlog^{2}{n})$，但其实可以去掉凸壳上二分这一步使得复杂度降一个$log$。
具体地，第一维按斜率$-frac{A_i}{B_i}$排序，然后在每个区间内将下标在$[l,mid]$的点扔到左边，$[mid+1,r]$的点扔到右边，其余步骤同上。
虽然左边和右边的下标都是乱序，但左边的任意下标都小于右边的任意下标，满足正确性。
此时由于斜率是单调的，可以将二分改成指针扫一遍，复杂度$O(nlog{n})$。
（不过既然我写了一发过了为什么还要再写一遍呢QwQ）
套路：
- 维护$x_{i}$不单调的凸壳$ ightarrow$Splay或CDQ分治。
- CDQ分治维护凸壳$ ightarrow$可以优化掉一个$log$。
代码：
#include<bits/stdc++.h> #define maxn 200005 #define maxm 500005 #define inf 0x7fffffff #define eps 1e-18 #define ll long long #define ld long double #define rint register int #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; struct node{ld f,a,b,r,k,x;ll id;}A[maxn],tp[maxn]; struct point{ ld x,y; ld operator*(const point b)const{return x*b.y-y*b.x;} point operator-(const point b){return (point){x-b.x,y-b.y};} }S[maxn]; ld F[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline bool cmp(node c,node d){return c.x<d.x;} inline bool cmp1(node c,node d){return c.id<d.id;} inline ld getk(point p){return p.y/p.x;} inline bool dcmp(ld x){return (abs(x)<=eps)?0:(x>0?1:-1);} inline ll find(ll n,ld k){ ll l=1,r=n,res=0; while(l<=r){ ll mid=l+r>>1; if((S[mid]-S[mid-1]).y>=k*(S[mid]-S[mid-1]).x) res=mid,l=mid+1; else r=mid-1; } return res; } inline void CDQ(ll l,ll r){ if(l==r){ A[l].f=max(A[l].f,F[A[l].id-1]),F[A[l].id]=A[l].f; A[l].x=A[l].f*A[l].r/(A[l].a*A[l].r+A[l].b); return; } ll mid=l+r>>1; CDQ(l,mid); ll top=0; S[0]=(point){0,-2e9}; for(rint i=l;i<=mid;i++){ ld nx=A[i].x,ny=nx/A[i].r; point now=(point){nx,ny}; while(top>1 && (now-S[top])*(S[top]-S[top-1])<=0) top--; S[++top]=now; } for(rint i=mid+1;i<=r;i++){ ll p=find(top,-A[i].a/A[i].b); A[i].f=max(A[i].f,A[i].a*S[p].x+A[i].b*S[p].y); } CDQ(mid+1,r); for(rint i=l;i<=r;i++){ A[i].f=max(A[i].f,F[A[i].id-1]),F[A[i].id]=A[i].f; A[i].x=A[i].f*A[i].r/(A[i].a*A[i].r+A[i].b); } sort(A+l,A+r+1,cmp); } int main(){ //freopen("cash7.in","r",stdin); //freopen("1.out","w",stdout); ll n=read(),s=read(); for(rint i=1;i<=n;i++) scanf("%Lf%Lf%Lf",&A[i].a,&A[i].b,&A[i].r),A[i].id=i; A[1].f=s,CDQ(1,n); sort(A+1,A+1+n,cmp1); printf("%Lf ",A[n].f); return 0; }