题解：P10557 [ICPC2024 Xi'an I] Dumb Robot

honglan0301 · 2024-06-01 21:38:20 · 题解

分析

对于一组 p,q，容易注意到期望得分是 \sum q_ip_ja_{i,j}。

那么当 p 给定时，我们记 v_i=\sum\limits_j p_ja_{i,j}，则期望得分 \geq 0 等价于 v_1q_1+v_2q_2+v_3q_3=(v_1-v_3)q_1+(v_2-v_3)q_2+v_3\geq 0，这是一个关于 q_1,q_2 的半平面。

因此只需求出每组 p 所限制的半平面的交集，再与 (q_1,q_2) 的取值范围（三角形 \{(0,0),(0,1),(1,0)\}）取交求面积即可，时间复杂度是半平面交所带来的 O(n\log n)。

代码

核心代码如下。halfcut 函数的作用是求出 A_i x+B_i y+C_i\geq 0 的半平面交。

double PolyArea(Point *P,int n);
int halfcut(Line *L,int n,Point *P);

signed main()
{
    cin>>ln;
    for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) cin>>a[i][j];
    for(int i=1;i<=ln;i++) for(int j=1;j<=3;j++) cin>>p[i][j];
    for(int i=1;i<=ln;i++)
    {
        for(int j=1;j<=3;j++)
        {
            for(int k=1;k<=3;k++)
            {
                val[i][j]+=p[i][k]*a[j][k];
            }
        }
        A[i]=val[i][1]-val[i][3]; B[i]=val[i][2]-val[i][3]; C[i]=val[i][3];
        //cout<<A[i]<<" "<<B[i]<<" "<<C[i]<<endl;
    }
    ln++; A[ln]=1; B[ln]=0; C[ln]=0;
    ln++; A[ln]=0; B[ln]=1; C[ln]=0;
    ln++; A[ln]=-1; B[ln]=-1; C[ln]=1;
    for(int i=1;i<=ln;i++) ins(A[i],B[i],C[i]); //Ax+By+C>=0
    if(!flag)
    {
        cout<<"0.0000000"<<endl; return 0;
    }
    int totd=halfcut(L,totl,as); //半平面交
    cout<<PolyArea(as,totd)/0.5<<endl; //凸包求面积
}