11722 Joining with Friend
You are going from Dhaka to Chittagong by train and you came to know one of your old friends is going
from city Chittagong to Sylhet. You also know that both the trains will have a stoppage at junction
Akhaura at almost same time. You wanted to see your friend there. But the system of the country is
not that good. The times of reaching to Akhaura for both trains are not fixed. In fact your train can
reach in any time within the interval [t1; t2] with equal probability. The other one will reach in any
time within the interval [s1; s2] with equal probability. Each of the trains will stop for w minutes after
reaching the junction. You can only see your friend, if in some time both of the trains is present in the
station. Find the probability that you can see your friend.
Input
The first line of input will denote the number of cases T (T < 500). Each of the following T line will
contain 5 integers t1, t2, s1, s2, w (360  t1 < t2 < 1080, 360  s1 < s2 < 1080 and 1  w  90). All
inputs t1, t2, s1, s2 and w are given in minutes and t1, t2, s1, s2 are minutes since midnight 00:00.
Output
For each test case print one line of output in the format ‘Case #k: p’ Here k is the case number and
p is the probability of seeing your friend. Up to 1e ?? 6 error in your output will be acceptable.
Sample Input
2
1000 1040 1000 1040 20
720 750 730 760 16
Sample Output
Case #1: 0.75000000
Case #2: 0.67111111

题意：

两个人到达车站的时间分别在时间区间t1~t2, s1~s2内；并且他们到站后都会停留ｗ分钟．问他们相遇的概率。

分析：

       以坐标(t1,s1),(t2,s2)作边平行于坐标轴的矩阵，再作直线y=x+w和y=x-w，它们之间与矩阵相覆盖的阴影面积占矩阵总面积比就是答案。过4个矩阵顶点作平行于y=x的直线，共分5个区域。分别根据w讨论y=x+w和y=x-w在哪个区域内，再计算非阴影面积，之后总面积减非阴影面积再除以总面积就可得到答案。

 1 #include <stdio.h> 2 #include <algorithm> 3 using namespace std; 4 int main(){ 5     int T,tt=0; 6     scanf("%d",&T); 7     while(T--){ 8         int a[10],t1,t2,s1,s2,w,i,j,k,p,x,y; 9         double s = 0,sum; //s记录非阴影面积10         scanf("%d%d%d%d%d",&t1,&t2,&s1,&s2,&w);11         a[0] = s1 - t2,a[1] = s2 - t2;12         a[2] = s1 - t1,a[3] = s2 - t1;13         sort(a,a + 4);14         sum = (t2 - t1) * (s2 - s1);15         p = min(s2 - s1,t2 - t1); // 短边16         if(-w <= a[0]) s += 0;17         else if(-w <= a[1])18             x = t2 - s1 - w, // 右点横坐标减去交点横坐标的值19             y = t2 - s1 - w,s += 0.5 * x * y; // 45度三角形20         else if(-w <= a[2])21             s += 0.5 * p * p,x = -w - a[1],s += x * p;22         else if(-w <= a[3])23             x = s2 + w - t1,y = s2 + w - t1,24             s += (t2 - t1) * (s2 - s1) - 0.5 * x * y;25         else s += (t2 - t1) * (s2 - s1);26         if(w >= a[3]) s += 0;27         else if(w >= a[2])28             y = x = s2 - w - t1,s += 0.5 * x * y;29         else if(w >= a[1])30             s += 0.5 * p * p,x = a[2] - w,s += x * p;31         else if(w >= a[0])32             y = x = t2 - s1 + w,s += (t2 - t1) * (s2 - s1) - 0.5 * x * y;33         else s += (t2 - t1) * (s2 - s1);34         printf("Case #%d: %.8lf\n",++tt,(sum - s) / sum);35     }36     return 0;37 }

View Code

UVa11722