C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 480K, 提交时间: 2019-01-07 17:01:24

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef double DB;
const int maxn=301, maxm=5010, inf = 100000000;
const DB zero = 1e-8;
int n, m, w, T, V, fs;
DB a[maxm];
struct line {DB x,y,len,k,L,R;} L[maxm];
struct inter {DB l,r;} c[maxn];

bool cmp(const inter &a, const inter &b) 
{return a.l<b.l || (a.l == b.l && a.r < b.r);}

DB f(DB x)
{
    DB s = 0; int p = 0;
    for (int i=1; i<=m; ++i)
    if (L[i].L<=x && x<=L[i].R)
    {
        c[++p].l = (x-L[i].x)*L[i].k+L[i].y; 
        c[p].r = c[p].l+L[i].len;
    }
    if (!p) return 0;
    sort(c+1, c+p+1, cmp);
    DB l = c[1].l, r = c[1].r;
    for (int i=2; i<=p; ++i)
    if (c[i].l>r) s += r-l, l = c[i].l, r = c[i].r;
    else r = max(c[i].r,r);
    s += r-l;
    return s;
}

inline DB area()
{
    DB s = 0;
    for (int i=2; i<=fs; ++i)
        s += (f(a[i])+f(a[i-1]))*(a[i]-a[i-1])/2;
    return s;
}

void check(DB x, DB y, DB len, DB v, DB t)
{
    L[++m].L = x, L[m].R = x+t, L[m].k = v;
    L[m].x = x, L[m].y = y, L[m].len = len;
    DB l = y+t*v, r = y+len+t*v;
    if (r>w+zero)
    {
        L[m].R = x+(w-len-y)/v; 
        check(L[m].R, w-len, len, -v, t-(w-len-y)/v);
    } else
    if (l<-zero)
    {
        L[m].R = x-y/v;
        check(L[m].R, 0, len, -v, t+y/v);
    } else a[++fs] = x+t;
    a[++fs] = x;
}

inline bool cross(int i, int j)
{
    return L[i].R>=L[j].L && L[i].L<=L[j].R && fabs(L[i].k-L[j].k)>zero;
}

void get_p(int i, int j)
{
    DB x1 = L[i].x, x2 = L[j].x, y1 = L[i].y, y2 = L[j].y;
    DB k1 = L[i].k, k2 = L[j].k, L1 = L[i].L, L2 = L[j].L;
    DB R1 = L[i].R, R2 = L[j].R, len1 = L[i].len, len2 = L[j].len;
    DB x = (y2-y1+x1*k1-x2*k2)/(k1-k2);
    if (L1<=x && x<=R1 && L2<=x && x<=R2) a[++fs] = x;
    x = (y2+len2-y1+x1*k1-x2*k2)/(k1-k2);
    if (L1<=x && x<=R1 && L2<=x && x<=R2) a[++fs] = x;
    x = (y2-len1-y1+x1*k1-x2*k2)/(k1-k2);
    if (L1<=x && x<=R1 && L2<=x && x<=R2) a[++fs] = x;
    x = (y2+len2-len1-y1+x1*k1-x2*k2)/(k1-k2);
    if (L1<=x && x<=R1 && L2<=x && x<=R2) a[++fs] = x;
}

int main()
{
    scanf("%d%d%d%d", &n, &w, &T, &V);
    for (int i=1; i<=n; ++i)
    {
        DB x, l, v;
        scanf("%lf%lf%lf", &x, &l, &v);
        if (x || l!=w) check(0,x,l,v,(DB) T);
        else {printf("0.00"); return 0;};
    }
    for (int i=1; i<=m; ++i)
    for (int j=1; j<=m; ++j)
        if (i!=j && cross(i,j)) get_p(i,j);
    sort(a+1, a+fs+1);
    printf("%.2lf\n", (T*w-area())*V);
    return 0;
}