斜率优化 cdq wa 80

#include <bits/stdc++.h>

int n, d[100005], q[100005], h;

double f[100005], x[100005], y[100005], a[100005], b[100005], rt[100005];

double slope(int id1, int id2){
  if(x[id1] >= x[id2]) return -1e100;
  return (y[id2] - y[id1]) / (x[id2] - x[id1]);
}

void cdq(int l, int r){
  if(l == r){
    f[l] = std::max(f[l], f[l - 1]);
    x[l] = rt[l] * f[l] / (rt[l] * a[l] + b[l]);
    y[l] = f[l] / (rt[l] * a[l] + b[l]);
    return ;
  }
  int mid = l + r >> 1;
  cdq(l, mid); 
  int c = mid - l + 1;
  for(int i = 1; i <= c; ++i) d[i] = i - 1 + l;
  std::sort(d + 1, d + c + 1, [&](int xx, int yy){
    if(x[xx] != x[yy]) return x[xx] < x[yy];
    return y[xx] > y[yy];
  });
  h = 0;
  for(int i = 1; i <= c; ++i){
    if(i > 1 && x[d[i]] == x[d[i - 1]] && y[d[i]] <= y[d[i - 1]]) continue;
    while(h >= 2 && slope(q[h - 1], q[h]) <= slope(q[h], d[i])) --h;
    q[h += 1] = d[i];
  }
  for(int i = mid + 1; i <= r; ++i){
    double slp = -a[i] / b[i];
    int L = 1, R = c, Mid;
    if(c == 1){
      f[i] = std::max(f[i], a[i] * x[q[1]] + b[i] * y[q[1]]);
      continue;
    }
    while(L < R){
      Mid = L + R >> 1;
      f[i] = std::max(f[i], a[i] * x[q[Mid]] + b[i] * y[q[Mid]]);
      if(Mid > 1 && slp >= slope(q[Mid - 1], q[Mid])) R = Mid;
      else L = Mid + 1;
    }
    f[i] = std::max(f[i], a[i] * x[q[L]] + b[i] * y[q[L]]);
  }
  cdq(mid + 1, r);
  return ;
}

int main(){
  scanf("%d%lf", &n, &f[0]);
  for(int i = 1; i <= n; ++i) scanf("%lf%lf%lf", &a[i], &b[i], &rt[i]);
  cdq(1, n);
  printf("%.5lf\n", f[n]);
  return 0;
}