自动搬运

查看原文

来自洛谷，原作者为

	K_srh 纵使日薄西山

搬运于2025-08-24 21:58:11，当前版本为作者最后更新于2024-02-03 01:52:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意：小凸晚上喜欢到操场跑步，今天他跑完两圈之后，他玩起了这样一个游戏。

操场是个凸 $n$ 边形，$n$ 个顶点按照逆时针从 $0 \sim n-1$ 编号。

现在小凸随机站在操场中的某个位置，标记为 $p$ 点。将 $p$ 点与 $n$ 个顶点各连一条边，形成 $n$ 个三角形。如果这时 $p$ 点，$0$ 号点，$1$ 号点形成的三角形的面积是 $n$ 个三角形中最小的一个，小凸则认为这是一次正确站位。现在小凸想知道他一次站位正确的概率是多少。

转化：求符合条件的区域面积占总面积的比

思路：一眼看过去，这和标签里的半平面交有啥关系啊，别着急，先推下柿子！

设第 $i$ 个顶点的坐标为 $A_i(x_i,y_i)$，可以用向量的叉乘表示下面积

$S_{\triangle A_1A_0P} = \frac{1}{2} \overrightarrow{A_0A_1} \times \overrightarrow{A_0P}$

$S_{\triangle A_{i+1}A_iP} = \frac{1}{2} \overrightarrow{A_iA_{i+1}} \times \overrightarrow{A_iP}$

因为 $S_{\triangle A_1A_0P} < S_{\triangle A_{i+1}A_iP}$（$i$ 从 $1$ 到 $n-1$）

所以有 $\overrightarrow{A_0A_1} \times \overrightarrow{A_0P} < \overrightarrow{A_iA_{i+1}} \times \overrightarrow{A_iP}$

设点 $P(x,y)$

我们将叉乘展开,即

$$(x_1-x_0)y + (y_0-y_1)x + x_0y_1-x_1y_0 < (x_{i+1}-x_i)y + (y_i-y_{i+1})x + x_iy_{i+1}-x_{i+1}y_i $$

将等式左边移到右边即为

$$(x_{i+1}-x_i-x_1+x_0)y + (y_i-y_{i+1}-y_0+y_1)x + (x_iy_{i+1}-x_{i+1}y_i-x_0y_1+x_1y_0) > 0 $$

对于所有 $1\leq i \leq n-1$ 成立（当 $i=n-1$ 时，$i+1$ 用 $0$ 替代）

这东西怎么这么眼熟，这不就是半平面交的解析式嘛！！！

把半平面的解析表达式转换成“向量左半平面”的表示形式，然后求半平面交即可。

另外还要记得 $P(x,y)$ 必须在凸多边形内部，所以凸多边形的边也要加进来一起做半平面交。

---

对于 $Ax+By+C>0$ 这里给出一种不会爆出 $0$ 导致奇怪错误的加线方式

$line(p,v)=((\frac{-C}{A*A+B*B}*A , \frac{-C}{A*A+B*B}*B) , (B,-A))$

（$p$ 是源点，$v$ 是方向向量，$line$ 是线的结构体数组）

接下来就是欢乐的代码环节啦！！！

#include<bits/stdc++.h>
#define debug(x) cerr<<__LINE__<<" : "<<#x<<"="<<(x)<<endl 
#define int long long
using namespace std;
const double eps=1e-12; 
const int N=3e5+5;
struct point{
	double x,y;
	point(double x=0,double y=0):x(x),y(y){};
	double lenght()
	{
		return sqrt(x*x+y*y);
	}
};
point operator * (const double &a, const point &b){
    return point(a*b.x, a*b.y);
}
int dcmp(double x)
{
	if(fabs(x)<eps)return 0;
	if(x<0)return -1;
	return 1;
}
point operator-(const point &a,const point &b)
{
	return point(a.x-b.x,a.y-b.y);
}
point operator+(const point &a,const point &b)
{
	return point(a.x+b.x,a.y+b.y);
}
bool operator<(const point &a,const point &b)
{
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double cross(point a,point b)
{
	return a.x*b.y-a.y*b.x;
}
double dot(point a,point b)
{
	return a.x*b.x+a.y*b.y;
}
struct Line{
	point A,v;
	double pol;
	Line(){};
	Line(const point &A,const point &v):A(A),v(v),pol(atan2(v.y,v.x)){};
	bool notleft(const point &B)const
	{
		return dcmp(cross(v,B-A))<=0;
	}
};
bool operator < (const Line &l,const Line &r)
{
	return dcmp(l.pol-r.pol)<0||(dcmp(l.pol-r.pol)==0&&dcmp(cross(l.v,r.A-l.A)<0));
	
}
point LineIns(const Line &l,const Line &r)
{
	double a1=cross(r.v,l.A-r.A);
	double a2=cross(r.v,l.A+l.v-r.A);
	double lam=a1/(a1-a2);
	return l.A+(lam*l.v);
}
int halfplane(Line l[],int n,Line hp[],point ins[])
{
	sort(l+1,l+1+n);
	int tot=0;
	for(int i=1;i<=n;i++)
	{
		if(tot&&dcmp(l[i].pol-l[tot].pol)==0)continue;
		l[++tot]=l[i];
	}
	int pl=1,pr=0;
	for(int i=1;i<=tot;i++)
	{
		while(pr-pl>=1&&l[i].notleft(ins[pr]))pr--;
		while(pr-pl>=1&&l[i].notleft(ins[pl+1]))pl++;		
		hp[++pr]=l[i];
		if(pr-pl>=1)ins[pr]=LineIns(hp[pr],hp[pr-1]);
	}
	while(pr-pl>=1&&hp[pl].notleft(ins[pr]))pr--;
	if(pr-pl>=2)ins[pl]=LineIns(hp[pl],hp[pr]);
	for(int i=pl;i<=pr;i++)
	{
		hp[i-pl+1]=hp[i];
		ins[i-pl+1]=ins[i];
	}
	return pr-pl+1;
}
double getarea(point p[],int n)
{
	double area=0;
	for(int i=2;i<=n-1;i++)
	{
		area+=cross(p[i]-p[1],p[i+1]-p[1]);
	}
	return area/2;
}
Line line[N],hp[N];
point p[N],ins[N],lp[N],pp[N]; 
signed main()
{
	int n,tot=0,cnt;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
	for(int i=1;i<=n;i++)
	{
		line[++tot]=Line(p[i],p[i%n+1]-p[i]);
	}
	double sum=getarea(p,n);
	for(int i=0;i<=n-1;i++)pp[i]=p[i+1];
	for(int i=1;i<=n-1;i++)
	{
		double A=pp[1].y-pp[0].y-pp[(i+1)%n].y+pp[i].y;
		double B=pp[0].x-pp[1].x+pp[(i+1)%n].x-pp[i].x;
		double C=pp[i].x*pp[(i+1)%n].y-pp[(i+1)%n].x*pp[i].y-pp[0].x*pp[1].y+pp[1].x*pp[0].y;
		line[++tot]=Line({-C/(A*A+B*B)*A,-C/(A*A+B*B)*B},{B,-A});
	}
	cnt=halfplane(line,tot,hp,ins);
	double pml=getarea(ins,cnt);
	printf("%.4lf",pml/sum);
	return 0;
}