JZOJ 4426 Stage

发表于 | 分类于 |

容易发现答案相当于每个团伙被监视的概率之和。

枚举一个团伙，以它为极点将所有教室按极角排序。
注意到不被监视的概率等价于存在一条经过这个团伙的直线，使得所有教室都在该直线一侧的概率。
按极角升序枚举一个教室，过当前团伙和这个教室作一条直线并将其顺时针旋转一个极小的角度，强制钦点这个教室出现（为了防止贡献算重），并令处于这条直线与这个教室相对的一侧的所有教室全部不出现，求和即可得到不被监视的概率。
（当然，还要计算没有教室被布控的概率。）

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e3;
const long double pi = acos(-1);
int n,m;
long double ans;
struct point
{
    long double x,y,p,angle;
    inline bool operator<(const point &o) const
    {
        return angle < o.angle;
    }
    inline long double operator*(const point &o) const
    {
        return x * o.y - y * o.x;
    }
} gang[N + 5],key[(N << 1) + 5];
long double calc(int g)
{
    long double ret,prod = 1;
    for(register int i = 1;i <= m;++i)
        key[i].angle = atan2(key[i].y - gang[g].y,key[i].x - gang[g].x);
    sort(key + 1,key + m + 1);
    for(register int i = 1;i <= m;++i)
        key[m + i] = key[i],key[m + i].angle += 2 * pi,prod *= 1 - key[i].p;
    ret = 1 - prod;
    for(register int i = 1,j = 1;i <= m;++i)
    {
        for(;key[j].angle - key[i].angle <= pi;prod /= 1 - key[j++].p);
        ret -= prod * key[i].p,prod *= 1 - key[i].p;
    }
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        scanf("%Lf%Lf",&gang[i].x,&gang[i].y);
    for(register int i = 1;i <= m;++i)
        scanf("%Lf%Lf%Lf",&key[i].x,&key[i].y,&key[i].p);
    for(register int i = 1;i <= n;++i)
        ans += calc(i);
    printf("%.10Lf\n",ans);
}