Convex Quadrilateral(ABC266 C)

题目描述：

给一个四边形坐标，判断它四个内角是不是都小c于180°，是则输出Yes，不是则输出No

思路1：

计算出每个内角的角度，考虑到c++中的asin和atan只能表示$[-\frac \pi 2,\frac \pi 2]$，所以用atan2来进行计算，它能表示$[-\pi,\pi]$.

得到所有角度以后只要有一个内角大于180°，则输出No

Code

void solve()
{
	PII A,B,C,D;
	cin >> A.x >> A.y;
	cin >> B.x >> B.y;
	cin >> C.x >> C.y;
	cin >> D.x >> D.y;
	
	PDD AB,AD,BC,BA,CB,CD,DC,DA;
	AB = {B.x - A.x,B.y - A.y};
	AD = {D.x - A.x,D.y - A.y};
	BC = {C.x - B.x,C.y - B.y};
	BA = {A.x - B.x,A.y - B.y};
	CB = {B.x - C.x,B.y - C.y};
	CD = {D.x - C.x,D.y - C.y};
	DC = {C.x - D.x,C.y - D.y};
	DA = {A.x - D.x,A.y - D.y};
	
	//AB * AD
	int a = (atan2(AD.y,AD.x) - atan2(AB.y,AB.x)) * 180.0 / PI;
	//BC * BA
	int b = (atan2(BA.y,BA.x) - atan2(BC.y,BC.x)) * 180.0 / PI;
	//CB * CD
	int c = (atan2(CB.y,CB.x) - atan2(CD.y,CD.x)) * 180.0 / PI;
	//DC * DA
	int d = (atan2(DC.y,DC.x) - atan2(DA.y,DA.x)) * 180.0 / PI;
	
	a = (a + 360) % 360;
	b = (b + 360) % 360;
	c = (c + 360) % 360;
	d = (d + 360) % 360;
	
	if (a >= 180 || b >= 180 || c >= 180 || d >= 180)	puts("No");
	else puts("Yes");
}

思路2：

思路1的想法很清晰，计算出所有角度再判断，但是这难免有些麻烦。所以我们可以考虑向量运算的性质。

向量叉乘：

$$\vec{a} =(x_1,y_1),\vec{b} = (x_2,y_2)$$

$$k = \vec a \times \vec b = |a| |b|\sin \theta = x_1y_2 - y_1x_2$$

当$k \lt 0$时，$\sin \theta < 0$，那么$a$正旋转到$b$的角度大于180°

当$k \gt 0$时，$\sin\theta \gt 0$，那么$a$正旋转到$b$的角度小于180°

利用这个性质我们也可以AC，并且比思路1更直接省事

int work(int x1,int y1,int x2,int y2)
{
	return x1*y2 - y1*x2;
}

void solve()
{
	PII A,B,C,D;
	cin >> A.x >> A.y;
	cin >> B.x >> B.y;
	cin >> C.x >> C.y;
	cin >> D.x >> D.y;
	
	PII AB,AD,BC,BA,CB,CD,DC,DA;
	AB = {B.x - A.x,B.y - A.y};
	AD = {D.x - A.x,D.y - A.y};
	BC = {C.x - B.x,C.y - B.y};
	BA = {A.x - B.x,A.y - B.y};
	CB = {B.x - C.x,B.y - C.y};
	CD = {D.x - C.x,D.y - C.y};
	DC = {C.x - D.x,C.y - D.y};
	DA = {A.x - D.x,A.y - D.y};
	
	if (work(AB.x,AB.y,AD.x,AD.y) < 0)
	{
		puts("No");
		return;
	}
	
	if (work(BC.x,BC.y,BA.x,BA.y) < 0)
	{
		puts("No");
		return;
	}
	
	if (work(CD.x,CD.y,CB.x,CB.y) < 0)
	{
		puts("No");
		return;
	}
	
	if (work(DA.x,DA.y,DC.x,DC.y) < 0)
	{
		puts("No");
		return;
	}
	
	puts("Yes");
}

由于本题让我对向量有了更深刻的理解，故记录下来