JDFZOJ2204:打地鼠 期望+凸包

思路:
首先\(O(n^3)\)的思路非常朴素,只需要考虑每条向量的贡献即可.向量的出现概率即为这两个点出现且向量右侧的点均不出现.于是我们需要暴力\(O(n)\)check右侧的点是否均不出现.

我们考虑以一个点为起点的所有向量的答案.

那么对于每一个向量右侧的点必定都是一段区间,且满足单调性.

我们枚举起点,然后把剩下的点按照关于起点的极角序排序,然后依次扫描即可.

当然有几个坑点:

概率有一些为0的不能直接乘除,而需要记录零的个数.

还有就是坑爹的三点共线问题.

我们考虑当角度相同时,按照距离从大到小排序.

然后扫描的时候进行一些特判.这里没太弄明白就先挖坑了.

(好像一开始先把点随机扰动一下应该也可以吧)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef double f2;
 
#define N 1010
struct Point{
    f2 x,y,p;
    Point(){}
    Point(f2 _x,f2 _y):x(_x),y(_y){}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator*(const f2&p)const{return Point(p*x,p*y);}
}P[N];
inline f2 sqr(const f2&x){return x*x;}
inline f2 cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}
inline f2 dot(const Point&a,const Point&b){return a.x*b.x+a.y*b.y;}
inline f2 length(const Point&a){return sqrt(sqr(a.x)+sqr(a.y));}
 
static const f2 eps=1e-8;
inline int dcmp(const f2&x){return fabs(x)<eps?0:(x<0?-1:1);}
 
struct Seg{
    Point v;
    f2 Ang,area,p,len;
    inline bool operator<(const Seg&B)const{
        return dcmp(Ang-B.Ang)==0?len>B.len:Ang<B.Ang;
    }
}S[N];
 
int main(){
    int n;scanf("%d",&n);register int i,j,k;
    for(i=0;i<n;++i)scanf("%lf%lf%lf",&P[i].x,&P[i].y,&P[i].p),P[i].p/=1000.0;
    f2 ans=0;
    for(i=0;i<n;++i){
        int id=0;
        for(j=0;j<n;++j)if(i^j){
            S[id].v=P[i]-P[j];
            S[id].Ang=atan2(S[id].v.y,S[id].v.x);
            S[id].area=cross(P[i],P[j]);
            S[id].p=P[j].p;
            S[id].len=length(S[id].v);
            id++;
        }
        sort(S,S+id);
        long double nowp=P[i].p;
        int zero=0;
        for(j=0;j<id;++j)if(dcmp(S[j].p-1)==0)++zero;else nowp*=(1-S[j].p);
         
        k=0;
        for(j=0;j<id;++j){
            while(dcmp(cross(S[j].v,S[k].v))>0||(dcmp(cross(S[j].v,S[k].v))==0&&dcmp(dot(S[k].v,S[j].v-S[k].v))<=0)){
                if(dcmp(1-S[k].p))nowp/=1-S[k].p;else --zero;
                k=(k+1)%id;
                if(k==j)break;
            }
            if(!zero)ans+=S[j].area*nowp*S[j].p;
            if(dcmp(1-S[j].p)!=0)nowp*=(1-S[j].p);else ++zero;
        }
    }
     
    printf("%.6lf",ans*.5);
    return 0;
}