题意：

略

见上一篇

题解：

方程还是那个方程f[i]=A[i] * X[j] + B[i] * Y[j]。

化简为Y[i]=(-A[i]/B[i]) * X[i] + f[i]/B[i]这一坨；

既然这个斜率不单调，那排个序让它单调不即可了；

排序之后的问题就是，在i前面更新i的点不一定能够更新i。而应该用来更新i的点说不定还在i的后面；

那么这时候就是用CDQ分治解决。

经典的四步先贴上来：

1.将操作依照时间划分为两个子区间。

2.递归处理左区间的改动与询问。

3.用左区间的改动处理右区间的询问；

4.递归处理右区间的改动与询问；

光这么四句话肯定没用，以下是详细的；

动态规划中对f[i]的更新相当于是查询，而用f[i]来更新别人则相当于是一次改动；

那么在将全部的点按斜率排序之后，进行一个分治的solve(1,n)，然后按四步走；

1.划分区间：

这里的时间就是天数，仅仅须要取一个mid然后用mid把点分成两堆。

注意这里划分了以后。两个区间仍按斜率有序。而且左区间的所有时间都小于右区间的所有时间；

2.递归处理左区间：

递归下去要有一个边界，这里的边界显然就是l==r的时候；

这时这个结点前面的结点都已经对它更新了；

所以它在更新一下f[i-1]就是终于的f[i]。顺便计算出X[i]Y[i]的值；

然后每层递归结束时要按X[i]排序(为了维护凸包方便)(这种递归结构下用归并的线性显然比快拍要好)；

3.用左区间改动右区间：

左区间已经按X[i]排序完毕，能够扫一遍求出凸包；

右区间如今还是按斜率排序。直接上斜率优化；

这时候右区间的全部点已经被左区间的点处理完了；

4.递归处理右区间：

被左区间处理了的点还要被右区间在它前面的点处理。所以再递归搞一下。

然后就结束了。f[n]就是答案。

这些操作全都是线性复杂度的，而一共递归有logn层。复杂度为O(nlogn)；

排完序之后的下标不是时间。

。。sort写错的去看眼科大夫。

。。

代码2k+，时间1232ms；

竟然没有平衡树跑得快，可是代码上的确是省了不少。

顺便一提。bz AC50题留念(笑)；

代码：

#include<math.h>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define N 110000

#define which(x)    (tr[tr[x].fa].ch[1]==x)

const double INF = 1e100;

const double EPS = 1e-8;

using namespace std;

struct node

{

    double x, y, slope;

    int no;

}a[N], temp[N];

double f[N], A[N], B[N], R[N];

int st[N];

int cmp(node a, node b)

{

    return a.slope < b.slope;

}

double slope(int x, int y)

{

    if (fabs(a[x].x - a[y].x) < EPS)

        return a[x].y < a[y].y ? INF : -INF;

    else

        return (a[x].y - a[y].y) / (a[x].x - a[y].x);

}

void merge(int l, int r)

{

    memcpy(temp + l, a + l, sizeof(node)*(r - l + 1));

    int mid = (l + r) >> 1, i, j, k;

    for (k = l, i = l, j = mid + 1; k <= r; k++)

    {

        if (i <= mid&&j <= r)

            a[k] = temp[i].x < temp[j].x ? temp[i++] : temp[j++];

        else

            a[k] = (i == mid + 1 ?

temp[j++] : temp[i++]);

    }

}

void slove(int l, int r)

{

    if (l == r)

    {

        f[l] = max(f[l], f[l - 1]);

        a[l].y = f[l] / (A[l] * R[l] + B[l]);

        a[l].x = R[l] * a[l].y;

    }

    else

    {

        int mid = (l + r) >> 1, i, j, k, top;

        for (i = l, j = l, k = mid + 1; i <= r; i++)

        if (a[i].no <= mid)

            temp[j++] = a[i];

        else

            temp[k++] = a[i];

        memcpy(a + l, temp + l, sizeof(node)*(r - l + 1));

        slove(l, mid);

        st[top = 1] = l;

        for (i = l + 1; i <= mid; i++)

        {

            while (top >= 2 && slope(st[top - 1], st[top]) < slope(st[top], i))

                top--;

            st[++top] = i;

        }

        for (i = mid + 1; i <= r; i++)

        {

            while (top >= 2 && slope(st[top - 1], st[top]) < a[i].slope)

                top--;

            f[a[i].no] = max(f[a[i].no], A[a[i].no] * a[st[top]].x + B[a[i].no] * a[st[top]].y);

        }

        slove(mid + 1, r);

        merge(l, r);

    }

}

int main()

{

    int n, i, j, k;

    double ans;

    scanf("%d%lf", &n, &f[1]);

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

        scanf("%lf%lf%lf", A + i, B + i, R + i),

        a[i].slope = -A[i] / B[i],

        a[i].no = i;

    sort(a + 1, a + n + 1, cmp);

    slove(1, n);

    printf("%.3lf", f[n]);

    return 0;

}