绝地求生

绝地求生

描述

绝地求生游戏的规则是，所有人从飞机上跳伞到荒岛上某个坐标，然后在这里相互厮杀，最后一个活下来的玩家获胜。

为了让游戏更丰富有趣，每一个时刻，一个圆形区域将会受到轰炸机的轰炸，我们可以认为，此时此刻，轰炸范围内的玩家都会阵亡。

TYZ著名颓废OI选手HJY今天和她的伙伴们一起玩吃鸡，但是HJY总是吃不到鸡（赢不了），因此她决定跟对手们一起比RP。

假设所有人在落地的一瞬间开始，就都站立不动，等待轰炸，每一个时刻，轰炸机都会在原先设定好的m个圆形轰炸区域中，等概率的选择其中一个轰炸区域，然后把这个区域内的活人全部炸死（在区域边缘也算炸死，如果半径为0，那么在轰炸点的位置也算被炸死）。当只剩下一个人活着，或者所有的人都被炸死（最后一次同时死掉）的时候，游戏结束。

注意：每次轰炸是随机选一个轰炸区域，一个区域可以被轰炸多次。

假设某次轰炸，炸死了K个人，那么，所有在这次轰炸之后还活着的人会得到K分。

HJY一开始就知道每个人的坐标以及每次轰炸的区域信息，请问，HJY在这次比赛中得分的期望值是多少呢？

/*************************************************************************
	> File Name: d.cpp
	> Author: Henry Chen
	> Mail: 390989083@qq.com 
	> Created Time: 四 10/ 1 11:35:17 2020
 ************************************************************************/

#include<bits/stdc++.h>
using namespace std;
struct people
{
	int x,y;
}p[20];
struct cir
{
	int x,y,r;
}ex[100001];
bool ck(people a,cir b)
{
	double dis = sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
	if(dis <= b.r) return 1;
	return 0;
}
int main()
{
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		scanf("%d%d",&p[i].x,&p[i].y);
	}
	for(int i = 1;i <= m;i++)
	{
		scanf("%d%d%d",&ex[i].x,&ex[i].y,&ex[i].r);
	}
	double ans = 0;
	for(int i = 2;i <= n;i++)
	{
		int sm1 = 0;
		int sm2 = 0;
		for(int j = 1;j <= m;j++)
		{
			if(!ck(p[1],ex[j]) && ck(p[i],ex[j]))
			{
				sm1++;
			}
			else if(ck(p[1],ex[j]))
			{
				sm2++;
			}
		}
		//printf("%d %d %d
",i,sm1,sm2);
		ans += sm1/1.0/(sm2+sm1);
	}
	//cout << ans << endl;
	printf("%.2lf
",ans);
	return 0;
}

 正解是状态压缩的期望dp，我这里使用的依赖每个人对于答案的期望贡献的独立性，分别统计。