UVA11722题解

happy_zero · 2023-06-22 16:04:10 · 题解

根据题意，我们可以用平面直角坐标系来表示到达的时间：

其中，黄色部分表示两人可以相遇，整个长方形就表示两人可能的到达，可以知道最后的概率就是 S_{\text{黄}}\div S_{\text{长}}。S_{\text{黄}} 不好求，但是可以用 S_{\text{红+黄}}-S_{\text{黄}}，而 S_{\text{红+黄}} 等于直线 y=x-w 上方与长方形重叠的面积，S_{\text{黄}} 等于直线 y=x+w 上方与长方形重叠的面积，于是问题可以转化为求一条直线上方与长方形重叠的面积，这一问题需要分类讨论，详见这里。

代码：

#include <bits/stdc++.h>
using namespace std;
double s1, s2, t1, t2, w;
double cal(int b)
{
    if (b <= s1 - t2) return 1.0 * (t2 - t1) * (s2 - s1);
    if (b >= s2 - t1) return 0;
    if (s1 - t2 <= b && b <= min(s1 - t1, s2 - t2)) return (s2 - s1) * (t2 - t1) - 0.5 * (t2 + b - s1) * (t2 + b - s1);
    if (max(s1 - t1, s2 - t2) <= b && b <= s2 - t1) return 0.5 * (s2 - t1 - b) * (s2 - t1 - b);
    if (s2 - t2 <= b && b <= s1 - t1) return 0.5 * (s2 + s1 - 2 * b - 2 * t1) * (s2 - s1);
    if (s1 - t1 <= b && b <= s2 - t2) return 0.5 * (2 * s2 - t1 - t2 - 2 * b) * (t2 - t1);
}
int main()
{
    int T, tot = 0;
    cin >> T;
    while (T--)
    {
        cin >> t1 >> t2 >> s1 >> s2 >> w;
        tot++;
        printf("Case #%d: %.7f\n", tot, (cal(-w) - cal(w)) * 1.0 / (s2 - s1) / (t2 - t1));
    }
    return 0;
 }