自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

搬运于2025-08-24 22:59:09，当前版本为作者最后更新于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; //凸包求面积
}