GWind概率求解皇星客栈

G-Wind

Problem Description

N棵树和M个蘑菇排成一排. 每棵树有自己的坐标和高度, 每个蘑菇有自己的坐标和权值. 一阵大风刮来, 每棵树有Li%的概率往左边倒, 有Ri%的概率往右边倒, 有(1 – Li% - Ri%)的概率不倒. 如果一棵高度为H坐标为X的树往左边倒下, 那么坐标在区间[X – H, X)内的蘑菇就会被砸到, 如果往右边倒下, 那么坐标在区间(X, X + H]内的蘑菇就会被砸到. 求不被树砸到的所有的蘑菇的权值之和的期望值。

Input

第一行包含2个整数N, M.
接下来N行, 每行4个整数X, H, L, R. 表示这棵树的坐标, 高度和往左右倒的概率. 即这棵树有L%的概率往左倒, R%的概率往右倒.
接下来M行, 每行2个整数Y, W. 表示这个蘑菇的坐标和权值.
[数据范围]
对于20% 的数据, 1 <= N, M <= 1000;
对于100% 的数据, 1 <= N <= 10^5, 1 <= M <= 10^4, 树和蘑菇的坐标的绝对值不超过10^9, 树的高度在[1, 10^9]范围内, 每个蘑菇的权值在[1, 1000]范围内, 每棵树的L,R 满足 0 <= L, R, L + R <= 100.

Output

输出一个整数, 为最后答案. 保留4位小数.

Sample Input

1 1
2 2 50 50
1 1

Sample Output

0.5000
第一种方法：比较暴力

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 typedef struct tree{
 5     int X;
 6     int H;
 7     double L;
 8     double R;
 9 }node;
10 node T[100001];
11 
12 typedef struct mogu{
13     int Y;
14     double W;
15 }mu;
16 mu Mo[10001];
17 
18 int cmp1( const void *a,const void *b )
19 {
20     node *aa = (node *)a;
21     node *bb = (node *)b;
22     return aa->X - bb->X;
23 }
24 
25 int cmp2( const void *a,const void *b )
26 {
27     mu *aa = (mu *)a;
28     mu *bb = (mu *)b;
29     return aa->Y - bb->Y;
30 }
31 
32 int main( )
33 {
34     int N;
35     int M;
36     int i;
37     int j;
38     double sum;
39     
40     while( scanf("%d %d",&N,&M) == 2 )
41     {
42         
43         sum = 0;
44         for( i = 0 ; i < N ; i++ )
45             scanf("%d %d %lf %lf",&T[i].X,&T[i].H,&T[i].L,&T[i].R);
46         for( i = 0 ; i < M ; i++ )
47             scanf("%d %lf",&Mo[i].Y,&Mo[i].W);
48         
49         qsort(T,N,sizeof(T[0]),cmp1);
50         qsort(Mo,M,sizeof(Mo[0]),cmp2);
51         
52         for( i = 0 ; i < N ; i++ )
53             for( j = 0 ; j < M ; j++ )
54             {
55                 if( Mo[j].Y < T[i].X-T[i].H )
56                     continue;
57                 else if( Mo[j].Y > T[i].X+T[i].H )
58                     continue;
59                 else{
60                     if( Mo[j].Y < T[i].X )
61                         Mo[j].W *= (1-T[i].L/100);
62                     else
63                         Mo[j].W *= (1-T[i].R/100);
64                 }
65             }
66             for( j = 0 ; j < M ; j++ )
67                 sum += Mo[j].W;
68             printf("%.4lf\n",sum);
69     }
70     return 0;
71 }