B - Bring Your Own Bombs Gym - 100519B（期望，离散化）

A sabotage platoon has completed its mission and planted some bombs on an enemy territory. Now they are about to report to their commanders how many enemy units will be destroyed. They have assigned this task to you.

The enemy territory is represented by a tile grid where the enemy platoons are located. Enemy units are standing in platoons that are represented by accurate rectangles, and they do not intersect each other. Each tile contains at most one enemy unit. Bombs have awesome firepower that can destroy all enemy units on the same tile line with the bomb: either horizontal or vertical, but not both. Unfortunately, all bombs are created manually by inexperienced engineers, and therefore, it is very hard to say how and if they explode or not. Only two values are known for certain for each bomb: p1, the probability that the bomb will explode horizontally, and p2, the probability that the bomb will explode vertically. It is implicitly known that with probability of 100% - p1 - p2 the bomb will not explode at all.

The sabotage platoon only plants the bombs outside the enemy platoons. Given the description of the enemy territory and planted bombs, you are to calculate the expected number of destroyed enemy units.

Input
The first line contains two integers N and M: the number of enemy platoons and bombs respectively (1 ≤ N, M ≤ 105).

The next N lines of input contain the descriptions of enemy platoons, one per line. Each platoon is described by four integers x1, y1, x2, y2: the coordinates of the tiles at the opposite corners of the rectangle (x1 ≤ x2, y1 ≤ y2).

Then the next M lines of input contain the description of bombs, one per line. Each bomb is described by integers x, y and numbers p1, p2: the coordinates of the tiles with bombs and the quality characteristics of the bombs given as an non-negative integer percentage respectively (p1 + p2 ≤ 100).

All coordinates do not exceed 109 by absolute value.

Output
Output must contain a single real number: the answer to the problem with absolute or relative error no more than 10 - 9.

Examples
Input
1 1
-1 -1 1 1
0 3 33 33
Output
0.990000000000000
Input
1 2
1 1 5 5
0 2 100 0
2 0 0 100
Output
9.000000000000000
Input
2 2
0 3 2 5
3 0 5 2
1 1 30 60
4 4 50 40
Output
4.980000000000000

题意：
有n个不相交区域，有m个炸弹。炸弹横向爆炸和纵向爆炸的概率告诉你了。求区域被炸到的期望个数。

思路：
如果可能的话，当然是沿着炸弹横向遍历一遍，纵向遍历一遍，更新经过格子的爆炸概率，最后把所有格子爆炸的概率相加就是结果。

本题数据很大，不允许这样做。于是我们可以离散化。
再对于每一个区域，找到横向（纵向）区域内的爆炸概率和。比如找到横向的爆炸概率和为p1,纵向为p2。那么这个区域内爆炸的期望数为$p1\ast (x2-x1+1)+p2\ast (y2-y1+1)-p1\ast p2$，其中$p1\ast p2$是重复的部分。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <string>
#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;

struct Node {
    int x1,y1,x2,y2;
}a[maxn];

int X[maxn],Y[maxn];
int b[maxn],c[maxn],fx[maxn],fy[maxn];
double dx[maxn],dy[maxn],sumx[maxn],sumy[maxn];

int main() {
    int n,m;scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) {
        scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
    }
    for(int i = 1;i <= m;i++) {
        scanf("%d%d",&X[i],&Y[i]);
        scanf("%d%d",&fy[i],&fx[i]); //fx代表垂直x轴，用x坐标代表
        b[i] = X[i];c[i] = Y[i];     //fy代表垂直y轴，用y坐标代表
    }
    sort(b + 1,b + 1 + m);sort(c + 1,c + 1 + m);
    int cnt1 = unique(b + 1,b + 1 + m) - b - 1;
    int cnt2 = unique(c + 1,c + 1 + m) - c - 1;

    for(int i = 1;i <= cnt1;i++) dx[i] = 1;
    for(int i = 1;i <= cnt2;i++) dy[i] = 1;
    
    for(int i = 1;i <= m;i++) {
        int pos1 = lower_bound(b + 1,b + 1 + cnt1,X[i]) - b;
        dx[pos1] *= (double)(100 - fx[i]) / 100.0;
        
        int pos2 = lower_bound(c + 1,c + 1 + cnt2,Y[i]) - c;
        dy[pos2] *= (double)(100 - fy[i]) / 100.0;
    }
    
    for(int i = 1;i <= cnt1;i++) {
        sumx[i] = sumx[i - 1] + (1 - dx[i]);
    }
    
    for(int i = 1;i <= cnt2;i++) {
        sumy[i] = sumy[i - 1] + (1 - dy[i]);
    }
    
    double ans = 0.0;
    
    for(int i = 1;i <= n;i++) {
        int x1 = a[i].x1,y1 = a[i].y1;
        int x2 = a[i].x2,y2 = a[i].y2;
        
        int p1 = lower_bound(b + 1,b + 1 + cnt1,x1) - b;
        int p2 = upper_bound(b + 1,b + 1 + cnt1,x2) - b - 1;
        ans += (sumx[p2] - sumx[p1 - 1]) * (y2 - y1 + 1);
        
        int p3 = lower_bound(c + 1,c + 1 + cnt2,y1) - c;
        int p4 = upper_bound(c + 1,c + 1 + cnt2,y2) - c - 1;
        ans += (sumy[p4] - sumy[p3 - 1]) * (x2 - x1 + 1);
        
        ans -= (sumx[p2] - sumx[p1 - 1]) * (sumy[p4] - sumy[p3 - 1]); //减掉重复的概率
    }
    
    printf("%.10f\n",ans);
    return 0;
}