题解：UVA11177 Fighting Against a Polygonal Monster

原题链接

• 洛谷 UVA11177 Fighting Against a Polygonal Monster

参考资料

• Atan2 - 维基百科

解题思路

随着圆的半径增大，能看到的面积单调不降，所以可以二分寻找满足条件的最小半径。

将多边形的每个顶点与原点连接，构成多个三角形。每个三角形都有一个对应圆心角的扇形。

通过分类讨论每个三角形与其对应扇形的交集面积，可以计算出能看到的面积。

函数定义

f1(A,B)

$f_1(A,B)$：表示三角形 $\triangle OAB$ 的有向面积。

通过向量叉积计算 $f_1$：

$$f_1(A,B)=\frac{\overrightarrow{OA}\times \overrightarrow{OB}}{2}$$

double f1(Point A,Point B)
{
	return Cross(A,B)/2;
}

f2(A,B,r)

$f_2(A,B,r)$：表示由 $OA$ 和 $OB$ 两条边围成且半径为 $r$ 的扇形的有向面积。

通过向量的叉积和点积计算出扇形的圆心角 $\theta=\angle AOB$：

$$\theta=\arctan\left(\frac{\sin\angle AOB}{\cos\angle AOB}\right)=\operatorname{atan2}(\overrightarrow{OA}\times \overrightarrow{OB},\overrightarrow{OA}\cdot \overrightarrow{OB})$$

根据扇形面积公式计算 $f_2$：

$$f_2(A,B,r)=\frac{\theta\cdot r^2}{2}=\frac{\operatorname{atan2}(\overrightarrow{OA}\times \overrightarrow{OB},\overrightarrow{OA} \cdot\overrightarrow{OB})\cdot r^2}{2}$$

double f2(Point A,Point B,double r)
{
	return atan2(Cross(A,B),Dot(A,B))*r*r/2;
}

calc(A,B,r)

$calc(A,B,r)$：表示每个三角形与其对应扇形的交集面积。

接下来通过分类讨论计算 $calc$，设：

$$S=calc(A,B,r)$$

分类讨论

Case #1

如果点 $A,B$ 距离圆心的距离都小于 $r$：

$$|\overrightarrow{OA}|\le r\land|\overrightarrow{OB}|\le r$$

此时扇形完全包含三角形，面积交集就是三角形的面积：

$$S=f_1(A,B)$$

if(Len(A)<=r&&Len(B)<=r)return f1(A,B);

判断相交

接下来我们需要判断直线 $AB$ 是否与圆有交点 $P$。

直线 $AB$ 的参数方程：

$$\overrightarrow{OP}=\overrightarrow{OA}+t\cdot\overrightarrow{AB}$$

代入圆的方程：

$$r=|\overrightarrow{OP}|=|\overrightarrow{OA}+t\cdot\overrightarrow{AB}|$$

整理为标准二次方程：

$$at^2+bt+c=0$$

计算方程的系数：

$$a=|AB|^2,b=2\cdot\overrightarrow{OA}\cdot\overrightarrow{AB},c=|OA|^2-r^2$$

double a=Len2(B-A),b=Dot(A,B-A)*2,c=Len2(A)-r*r;

计算判别式 $\Delta$：

$$\Delta=b^2-4ac$$

double d=b*b-a*c*4;

Case #2

如果直线与圆没有交点或相切：

$$\Delta\le 0$$

此时三角形完全包含扇形，面积交集就是扇形的面积：

$$S=f_2(A,B,r)$$

if(d<=0)return f2(A,B,r);

计算交点

接下来通过求根公式，计算出 $t$：

$$t_1=\frac{-b-\sqrt{\Delta}}{2a},t_2=\frac{-b+\sqrt{\Delta}}{2a}$$

double t1=(-b-sqrt(d))/(a*2),t2=(-b+sqrt(d))/(a*2);

代入直线方程，计算出直线与圆的交点 $P$：

$$\overrightarrow{OP}=\overrightarrow{OA}+t\cdot\overrightarrow{AB}$$

我们令距离 $A$ 较近的交点为 $C$，距离 $B$ 较近的交点为 $D$：

$$\overrightarrow{OC}=\overrightarrow{OA}+t_1\cdot\overrightarrow{AB},\overrightarrow{OD}=\overrightarrow{OA}+t_2\cdot\overrightarrow{AB}$$

Point C=A+(B-A)*t1,D=A+(B-A)*t2;

Case #3

如果点 $C,D$ 都在点 $A,B$ 的同一侧（即线段 $AB$ 的延长线上）：

$$t_1\ge 1\lor t_2\le 0$$

此时三角形也完全包含扇形，面积交集就是扇形的面积：

$$S=f_2(A,B,r)$$

if(t1>=1||t2<=0)return f2(A,B,r);

Case #4

如果点 $D$ 在线段 $AB$ 上：

$$t_1\le 0$$

此时 $AD$ 是三角形面积，$DB$ 是扇形面积：

$$S=f_1(A,D)+f_2(D,B,r)$$

if(t1<=0)return f1(A,D)+f2(D,B,r);

Case #5

如果点 $C$ 在线段 $AB$ 上：

$$t_2\ge 1$$

此时 $AC$ 是扇形面积，$CB$ 是三角形面积：

$$S=f_2(A,C,r)+f_1(D,B)$$

if(t2>=1)return f2(A,C,r)+f1(C,B);

Case #6

否则点 $C,D$ 都在线段 $AB$ 上。

此时 $AC$ 是扇形面积，$CD$ 是三角形面积，$DB$ 是扇形面积：

$$S=f_2(A,C,r)+f_1(C,D)+f_2(D,B,r)$$

return f2(A,C,r)+f1(C,D)+f2(D,B,r);

参考代码

#include <bits/stdc++.h>
using namespace std;

const double eps=1e-8;
const int N=55;
struct Point
{
	double x,y;
	Point(){}
	Point(double _x,double _y):x(_x),y(_y){}
	Point operator+(Point B){return Point(x+B.x,y+B.y);}
	Point operator-(Point B){return Point(x-B.x,y-B.y);}
	Point operator*(double k){return Point(x*k,y*k);}
}a[N];
double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
double Len(Point A){return sqrt(Dot(A,A));}
double Len2(Point A){return Dot(A,A);}
double f1(Point A,Point B){return Cross(A,B)/2;}
double f2(Point A,Point B,double r){return atan2(Cross(A,B),Dot(A,B))*r*r/2;}
double calc(Point A,Point B,double r)
{
	if(Len(A)<=r&&Len(B)<=r)return f1(A,B);
	double a=Len2(B-A),b=Dot(A,B-A)*2,c=Len2(A)-r*r;
	double d=b*b-a*c*4;
	if(d<=0)return f2(A,B,r);
	double t1=(-b-sqrt(d))/(a*2),t2=(-b+sqrt(d))/(a*2);
	Point C=A+(B-A)*t1,D=A+(B-A)*t2;
	if(t1>=1||t2<=0)return f2(A,B,r);
	if(t1<=0)return f1(A,D)+f2(D,B,r);
	if(t2>=1)return f2(A,C,r)+f1(C,B);
	return f2(A,C,r)+f1(C,D)+f2(D,B,r);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int $=0,n=0;
	while(cin>>n&&n)
	{
		double s;
		cin>>s;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].x>>a[i].y;
		}
		double l=0,r=10000;
		while(r-l>eps)
		{
			double mid=(l+r)/2,sum=0;
			for(int i=1;i<=n;i++)
			{
				sum+=calc(a[i],a[i%n+1],mid);
			}
			if(fabs(sum)>=s)r=mid;
			else l=mid;
		}
		cout<<"Case "<<(++$)<<": "<<fixed<<setprecision(2)<<l<<'\n';
	}
	return 0;
}