Gym - 100519B [离散+逆向思维+概率计算]

题目链接:https://vjudge.net/problem/Gym-100519B

 

解题思路:

如果这题先放置矩形，然后再去查找爆炸的直线与矩形的交，那么还要容斥，似乎就做不了了。

那么我们不如先去放爆炸点，离散并算出每条直线会爆炸的总的概率。然后再去查询一个矩形，那么对于竖向爆炸每条的爆炸长度不就是等于矩形的宽吗，横向爆炸每条的长度也就是矩形的长了。然后就需要先预处理要前缀和的横向爆炸概率和前缀和竖向概率。之后答案就是sum(竖向概率和)*len(矩形的宽) + sum(横向概率和)*(矩形的长)。

但这还不是最后的答案，因为在横向和竖向的交叉点上每个都都算了p1(该竖向爆炸概率)*p2(该横向爆炸概率)。

所以最后再减去sum(竖向概率和)*sum(横向概率和)就是最后的答案了。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int mx = 1e5+10;
int n,m,K;
int x1[mx],x2[mx],x3[mx];
int y1[mx],y2[mx],y3[mx];
int a[mx],b[mx],fx[mx],fy[mx];
double dx[mx],dy[mx];
double px[mx],py[mx];	
int main(){
	scanf("%d%d",&n,&m);
	int cx = 1,cy = 1;
	for(int i=1;i<=n;i++){
		scanf("%d%d",x1+i,y1+i);
		scanf("%d%d",x2+i,y2+i);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",x3+i,y3+i);
		scanf("%d%d",fy+i,fx+i);
		a[cx++] = x3[i];
		b[cy++] = y3[i];
	}
	sort(a+1,a+cx);sort(b+1,b+cy);
	cx = unique(a+1,a+cx) - a;
	cy = unique(b+1,b+cy) - b;
	for(int i=1;i<max(cx,cy);i++)
	dx[i] = dy[i] = 1;
	for(int i=1;i<=m;i++){
		int x = lower_bound(a+1,a+cx,x3[i]) - a;
		dx[x] *= (100.0-fx[i])/100;
		int y = lower_bound(b+1,b+cy,y3[i]) - b;
		dy[y] *= (100.0-fy[i])/100;
	}
	for(int i=1;i<cx;i++) dx[i] = 1 - dx[i],px[i] = px[i-1]+dx[i];
	for(int i=1;i<cy;i++) dy[i] = 1 - dy[i],py[i] = py[i-1]+dy[i];
	double ans = 0;
	for(int i=1;i<=n;i++){
		int l1 = lower_bound(a+1,a+cx,x1[i]) - a;
		int r1 = upper_bound(a+1,a+cx,x2[i]) - a - 1;
		int l2 = lower_bound(b+1,b+cy,y1[i]) - b;
		int r2 = upper_bound(b+1,b+cy,y2[i]) - b - 1;
		double sumx = px[r1] - px[l1-1];
		double sumy = py[r2] - py[l2-1];
		ans += sumx*(y2[i]-y1[i]+1)+sumy*(x2[i]-x1[i]+1) - sumx*sumy;
	}
	printf("%.8lf\n",ans);
	return 0;
}