记录编号	267114	评测结果	AAAATTTAAA
题目名称	[NOI 2007]货币兑换	最终得分	70
用户昵称	TenderRun	是否通过	未通过
代码语言	C++	运行时间	3.469 s
提交时间	2016-06-10 17:37:37	内存使用	4.51 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const double eps=1e-8;
const double INF=1e20;
const int maxn=100010;
double X[maxn],Y[maxn],lk[maxn],rk[maxn],ans;

int ch[maxn][2],fa[maxn],rt,cnt,tot,n;

double fabs(double x){return (x>0)?x:-x;}

void Rotate(int x){
	int y=fa[x],g=fa[y],c=ch[y][1]==x;
	ch[y][c]=ch[x][c^1];fa[ch[y][c]]=y;
	ch[x][c^1]=y;fa[y]=x;fa[x]=g;
	if(g)ch[g][ch[g][1]==y]=x;
}

void Splay(int x,int g=0){
	for(int y;(y=fa[x])!=g;Rotate(x))
		if(fa[y]!=g)Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x);
	if(!g)rt=x;	
}

double Get_K(int j,int k){
	if(fabs(X[j]-X[k])<=eps)return INF;
	else return (Y[j]-Y[k])/(X[j]-X[k]);
}

int Get_Prev(){
	int p=ch[rt][0],ret=p;
	while(p){
		if(Get_K(rt,p)+eps>=lk[p])p=ch[p][0];
		else ret=p,p=ch[p][1];
	}
	return ret;
}

int Get_Succ(){
	int p=ch[rt][1],ret=p;
	while(p){
		if(Get_K(p,rt)<=rk[p]+eps)p=ch[p][1];
		else ret=p,p=ch[p][0];
	}
	return ret;
}

void Insert(double x,double y){
	int p=rt,pre=rt,l,r;
	while(p){
		pre=p;
		if(X[p]+eps>=x)p=ch[p][0];
		else p=ch[p][1];
	}
	p=++cnt;
	if(!rt)rt=p;
	ch[pre][X[pre]+eps<x]=p;
	fa[p]=pre;X[p]=x;Y[p]=y;
	
	Splay(p);
	if(ch[p][0]){
		l=Get_Prev();
		Splay(l,rt);ch[l][1]=0;
		rk[l]=lk[p]=Get_K(p,l);
	}
	else lk[p]=INF;
	if(ch[p][1]){
		r=Get_Succ();
		Splay(r,rt);ch[r][0]=0;
		rk[p]=lk[r]=Get_K(r,p);
	}
	else rk[p]=-INF;
	if(lk[p]<=rk[p]+eps){
		rt=ch[p][0];ch[rt][1]=ch[p][1];
		fa[ch[rt][1]]=rt;
		rk[rt]=lk[ch[rt][1]]=Get_K(ch[rt][1],rt);
	}
}

int Get_Pos(double k){
	int p=rt;
	while(p){
		if(lk[p]+eps>=k&&k+eps>=rk[p])break;
		if(lk[p]<k+eps)p=ch[p][0];
		else p=ch[p][1];
	}
	return p;
}

void Debug(int p){
	if(!p)return;
	Debug(ch[p][0]);
	printf("<%f >",lk[p]);
	Debug(ch[p][1]);
}

double Get_Ans(double a,double b){
	int p=Get_Pos(-b/a);
	return a*Y[p]+b*X[p];
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("cash.in","r",stdin);
	freopen("cash.out","w",stdout);
#endif
	double a,b,rate;
	scanf("%d%lf",&n,&ans);
	for(int i=1;i<=n;i++){
		scanf("%lf%lf%lf",&a,&b,&rate);
		if(i!=1)ans=max(ans,Get_Ans(a,b));
		Insert(ans/(rate*a+b),ans/(a+b/rate));
		
	//	printf("\n");
	//	Debug(rt);
	//	printf("\n");
		
	}
	printf("%.3f\n",ans);
	return 0;
}

/* 
10 100
5.007 5.139 1.44
5.142 5.963 1.39
5.248 5.038 1.06
5.705 5.606 1.07
5.151 5.067 1.86
5.924 5.979 1.88
5.069 5.912 1.28
5.075 5.092 1.77
5.485 5.409 1.28
5.161 5.233 1.63

148.311
*/