题解：UVA11177 Fighting Against a Polygonal Monster
lailai0916
·
·
题解
参考资料
解题思路
随着圆的半径增大，能看到的面积单调不降，所以可以二分寻找满足条件的最小半径。
将多边形的每个顶点与原点连接，构成多个三角形。每个三角形都有一个对应圆心角的扇形。
通过分类讨论每个三角形与其对应扇形的交集面积，可以计算出能看到的面积。
函数定义
f1(A,B)
通过向量叉积计算 $f_1$：
$$
f_1(A,B)=\frac{\overrightarrow{OA}\times \overrightarrow{OB}}{2}
$$
```cpp
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}
$$
```cpp
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)
$$
```cpp
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
$$
```cpp
double a=Len2(B-A),b=Dot(A,B-A)*2,c=Len2(A)-r*r;
```
计算判别式 $\Delta$：
$$
\Delta=b^2-4ac
$$
```cpp
double d=b*b-a*c*4;
```
### Case 2
如果直线与圆没有交点或相切：
$$
\Delta\le 0
$$
此时三角形完全包含扇形，面积交集就是扇形的面积：
$$
S=f_2(A,B,r)
$$
```cpp
if(d<=0)return f2(A,B,r);
```
### 计算交点
接下来通过求根公式，计算出 $t$：
$$
t_1=\frac{-b-\sqrt{\Delta}}{2a},t_2=\frac{-b+\sqrt{\Delta}}{2a}
$$
```cpp
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}
$$
```cpp
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)
$$
```cpp
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)
$$
```cpp
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)
$$
```cpp
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)
$$
```cpp
return f2(A,C,r)+f1(C,D)+f2(D,B,r);
```
## 参考代码
```cpp
#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;
}
```