CDQWA47与答案微小偏差
查看原帖
CDQWA47与答案微小偏差
515891
paper_楼主2024/7/19 09:25
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
#define int long long
#define double long double
double dp[N], eps = 1e-9;
int n, m, q[N];
double k[N], b[N], X[N], Y[N];
struct P {
	int x, r, v, id;
	double R;
}s[N], w[N];
void CTQ(int l, int r) {
	if (l >= r) return;
	int mid = l + r >> 1;
	CTQ(l, mid);
	int hh = 1, tt = 0;
	for (int i = l; i <= mid; i ++ ) X[i] = s[i].R, Y[i] = dp[s[i].id] - s[i].x * s[i].R;
	for (int i = l; i <= mid; i ++ ) {
		while (hh < tt && (Y[i] - Y[q[tt - 1]]) * (X[q[tt]] - X[q[tt - 1]]) - (Y[q[tt]] - Y[q[tt - 1]]) * (X[i] - X[q[tt - 1]]) < eps) tt --;
		q[++tt] = i;
	}
	for (int i = mid + 1; i <= r; i ++ ) {
		while (hh < tt && (Y[q[hh + 1]] - Y[q[hh]]) - (double)-s[i].x * (X[q[hh + 1]] - X[q[hh]]) < eps) hh ++;
		dp[i] = min(dp[i], Y[q[hh]] + X[q[hh]] * s[i].x + s[i].v);
	}
	int i = l, j = mid + 1, C = 0;
	CTQ(mid + 1, r);
	while (i <= mid && j <= r) {
		if (s[i].R <= s[j].R) w[++C] = s[i ++ ];
		else w[++C] = s[j ++ ];
	}
	while (i <= mid) w[++C] = s[i ++ ];
	while (j <= r) w[++C] = s[j ++ ];
	for (i = l; i <= r; i ++ ) s[i] = w[i - l + 1];
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++ ) cin >> s[i].x >> s[i].r >> s[i].v, s[i].R = (double)1 / 2 / sqrt(s[i].r), s[i].id = i;
	for (int i = 0; i < N; i ++ ) dp[i] = 1e18;dp[1] = s[1].v;
	CTQ(1, n);
	double ans = 1e18;
	for (int i = 1; i <= n; i ++ )
		if (s[i].x + s[i].r >= m) ans = min(ans, dp[s[i].id]);
	printf("%.3Lf", ans);
	return 0;
}
2024/7/19 09:25
加载中...