UVa 11722 Joining with Friend (几何概率 + 分类讨论)

题意：某两个人 A，B 要在一个地点见面，然后 A 到地点的时间区间是 [t1, t2]，B 到地点的时间区间是 [s1, s2]，他们出现的在这两个区间的每个时刻概率是相同的，并且他们约定一个到了地点，等待另一个人 w 分钟，问你他们可能见面的概率是多少。

析：就是一个高中的一个几何概率的典型例题，他们相遇的条件是 |s -t | <= w，然后在画出二维图，再求面积即可，现在问题的情况是有好多种，所以需要我们进行分类讨论，答案其实就是下面那条直线上面的在矩形内的面积减去上面那条直线上面的在矩形的面积，所以只要求出这个两个面积即可。首先分类讨论，先把下面那条直线上面的在矩形内的面积放到一个函数里，然后再分类讨论上面即可，具体看代码，可以画画图，理解一下。

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

#include <cmath>

#include <stack>

#include <sstream>

#include <list>

#include <assert.h>

#include <bitset>

#include <numeric>

#define debug() puts("++++")

#define gcd(a, b) __gcd(a, b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define fi first

#define se second

#define pb push_back

#define sqr(x) ((x)*(x))

#define ms(a,b) memset(a, b, sizeof a)

#define sz size()

#define pu push_up

#define pd push_down

#define cl clear()

#define lowbit(x) -x&x

//#define all 1,n,1

#define FOR(i,x,n)  for(int i = (x); i < (n); ++i)

#define freopenr freopen("in.in", "r", stdin)

#define freopenw freopen("out.out", "w", stdout)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const LL LNF = 1e17;

const double inf = 1e20;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int maxn = 1000 + 10;

const int maxm = 100 + 2;

const LL mod = 100000000;

const int dr[] = {-1, 1, 0, 0, 1, 1, -1, -1};

const int dc[] = {0, 0, 1, -1, 1, -1, 1, -1};

const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};

int n, m;

const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

inline bool is_in(int r, int c) {

  return r >= 0 && r < n && c >= 0 && c < m;

}

inline int up_line(int t, int w){ return t + w; }

inline int up_line_x(int s, int w){ return s - w; }

inline int down_line(int t, int w){ return t - w; }

inline int down_line_x(int s, int w){ return s + w; }

double down_line_area(int s1, int s2, int t1, int t2, int w){

  double denominator = (t2 - t1) * (s2 - s1);

  if(down_line(t1, w) >= s2)  return 0.;

  if(down_line(t2, w) <= s1)  return denominator;

  if(down_line(t1, w) <= s1 && down_line(t2, w) <= s2){  // the down line is under the diagonal of the rectangle

    int x = t2 - down_line_x(s1, w);

    int y = down_line(t2, w) - s1;

    return denominator - x * y / 2.;

  }

  if(down_line(t1, w) >= s1 && down_line(t2, w) >= s2){  // the down line is on the diagonal of the rectangle

    int x = down_line_x(s2, w) - t1;

    int y = s2 - down_line(t1, w);

    return x * y / 2.;

  }

  // the down line intersect with diagonal of the rectangle

  if(down_line(t1, w) <= s1 && down_line(t2, w) >= s2){

    int x = down_line_x(s1, w) - t1 + down_line_x(s2, w) - t1;

    int y = s2 - s1;

    return x * y / 2.;

  }

  int x = t2 - t1;

  int y = s2 - down_line(t1, w) + s2 - down_line(t2, w);

  return x * y / 2.;

}

int main(){

  int T;  cin >> T;

  for(int kase = 1; kase <= T; ++kase){

    int s1, s2, t1, t2, w;

    scanf("%d %d %d %d %d", &t1, &t2, &s1, &s2, &w);

    double denominator = (t2 - t1) * (s2 - s1);

    printf("Case #%d: ", kase);

    if(up_line(t2, w) <= s1) printf("0\n");  // the up line under the rectangle

    else if(up_line(t1, w) >= s2)  // the up line on the rectangle

      printf("%.6f\n", down_line_area(s1, s2, t1, t2, w) / denominator);

    else if(up_line(t1, w) <= s1 && up_line(t2, w) <= s2){  // the up line is under the diagonal of the rectangle

      int x = t2 - up_line_x(s1, w);

      int y = up_line(t2, w) - s1;

      printf("%.6f\n", (down_line_area(s1, s2, t1, t2, w) - denominator + x * y / 2.) / denominator);

    }

    else if(up_line(t1, w) >= s1 && up_line(t2, w) >= s2){  // the up line is on the diagonal of the rectangle

      int x = up_line_x(s2, w) - t1;

      int y = s2 - up_line(t1, w);

      printf("%.6f\n", (down_line_area(s1, s2, t1, t2, w) - x * y / 2.) / denominator);

    }

    // the up line intersect with diagonal of the rectangle

    else if(up_line(t1, w) <= s1 && up_line(t2, w) >= s2){

      int x = up_line_x(s1, w) - t1 + up_line_x(s2, w) - t1;

      int y = s2 - s1;

      printf("%.6f\n", (down_line_area(s1, s2, t1, t2, w) - x * y / 2.) / denominator);

    }

    else{

      int x = t2 - t1;

      int y = s2 - up_line(t1, w) + s2 - up_line(t2, w);

      printf("%.6f\n", (down_line_area(s1, s2, t1, t2, w) - x * y / 2.) / denominator);

    }

  }

  return 0;

}

UVa 11722 Joining with Friend (几何概率 + 分类讨论)的相关教程结束。