2010-1165

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

by vout
[[BR]]
给定x, y, a, b, k，随机输出范围在[0, a]和[0, b]的两个数p和q，求满足|x + y - (p + q)| <= k的概率。
[[BR]]
分三种情况考虑，以下不妨总设a > b：
[[BR]]
1. a = b = 0. 在这种情况下，必然有p = q = 0，因此只需要判断x + y <= k是否成立即可。这里有一个double的精度问题，要加eps判断：x + y <= k + eps。
[[BR]]
2. a > 0 而 b = 0. 必然有q = 0，只要判断p的取值范围，变为线段上的几何概型问题。
[[BR]]
3. a > 0 && b > 0. 此时p和q可取的区域为[0, a] * [0, b]的矩形，变为矩形上的几何概型问题。
[[BR]]
代码如下：[[BR]]

{{{
#!cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;

const double eps = 1e-8;

int main() {
    double x, y, a, b, k;
    while (scanf("%lf%lf%lf%lf%lf", &x, &y, &a, &b, &k) != EOF) {
        if (a < b) {
            swap(a, b);
        }

        if (a == 0) {
            if (x + y <= k + eps) {
                printf("%.6f\n", 1.0);
            } else {
                printf("%.6f\n", 0.0);
            }
            continue;
        }

        double d = x + y;

        if (b == 0) {
            double l = min(max(0.0, d - k), a);
            double r = max(0.0, min(a, d + k));
            printf("%.6f\n", fabs(r - l) / a);
            continue;
        }

        double p1 = d + k;
        double p2 = d + k - b;
        double p3 = d + k;
        double p4 = d + k - a;

        double s1 = 0;

        if (p1 <= 0) {
            s1 = 0;
        } else if (p1 <= b) {
            s1 = 0.5 * p1 * p1;
        } else if (p1 <= a) {
            s1 = 0.5 * p1 * p1 - 0.5 * (p1 - b) * (p1 - b);
        } else if (p1 <= a + b) {
            s1 = a * b - 0.5 * (a + b - p1) * (a + b - p1);
        } else {
            s1 = a * b;
        }

        p1 = d - k;
        p2 = d - k - b;
        p3 = d - k;
        p4 = d - k - a;


        if (p1 <= 0) {
            s1 = s1;
        } else if (p1 <= b) {
            s1 -= 0.5 * p1 * p1;
        } else if (p1 <= a) {
            s1 -= 0.5 * p1 * p1 - 0.5 * (p1 - b) * (p1 - b);
        } else if (p1 <= a + b) {
            s1 -= a * b - 0.5 * (a + b - p1) * (a + b - p1);
        } else {
            s1 -= a * b;
        }

        printf("%.6f\n", fabs(s1) / a / b);
    }
    return 0;
}

}}}

by vout

给定x, y, a, b, k，随机输出范围在[0, a]和[0, b]的两个数p和q，求满足|x + y - (p + q)| <= k的概率。

分三种情况考虑，以下不妨总设a > b：

1. a = b = 0. 在这种情况下，必然有p = q = 0，因此只需要判断x + y <= k是否成立即可。这里有一个double的精度问题，要加eps判断：x + y <= k + eps。

2. a > 0 而 b = 0. 必然有q = 0，只要判断p的取值范围，变为线段上的几何概型问题。

3. a > 0 && b > 0. 此时p和q可取的区域为[0, a] * [0, b]的矩形，变为矩形上的几何概型问题。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
const double eps = 1e-8;
int main() {
    double x, y, a, b, k;
    while (scanf("%lf%lf%lf%lf%lf", &x, &y, &a, &b, &k) != EOF) {
        if (a < b) {
            swap(a, b);
        }
        if (a == 0) {
            if (x + y <= k + eps) {
                printf("%.6f\n", 1.0);
            } else {
                printf("%.6f\n", 0.0);
            }
            continue;
        }
        double d = x + y;
        if (b == 0) {
            double l = min(max(0.0, d - k), a);
            double r = max(0.0, min(a, d + k));
            printf("%.6f\n", fabs(r - l) / a);
            continue;
        }
        double p1 = d + k;
        double p2 = d + k - b;
        double p3 = d + k;
        double p4 = d + k - a;
        double s1 = 0;
        if (p1 <= 0) {
            s1 = 0;
        } else if (p1 <= b) {
            s1 = 0.5 * p1 * p1;
        } else if (p1 <= a) {
            s1 = 0.5 * p1 * p1 - 0.5 * (p1 - b) * (p1 - b);
        } else if (p1 <= a + b) {
            s1 = a * b - 0.5 * (a + b - p1) * (a + b - p1);
        } else {
            s1 = a * b;
        }
        p1 = d - k;
        p2 = d - k - b;
        p3 = d - k;
        p4 = d - k - a;
        if (p1 <= 0) {
            s1 = s1;
        } else if (p1 <= b) {
            s1 -= 0.5 * p1 * p1;
        } else if (p1 <= a) {
            s1 -= 0.5 * p1 * p1 - 0.5 * (p1 - b) * (p1 - b);
        } else if (p1 <= a + b) {
            s1 -= a * b - 0.5 * (a + b - p1) * (a + b - p1);
        } else {
            s1 -= a * b;
        }
        printf("%.6f\n", fabs(s1) / a / b);
    }
    return 0;
}