题解：P8718 [蓝桥杯 2020 省 A2] 荒岛探测
CChord
·
·
题解
题意
求一个椭圆与一个三角形相交部分的面积。
整体思路
-
几何变换，简化椭圆方程。
-
数值积分，将交集区域的面积近似为多个小矩形的面积之和。
几何变换
考虑将椭圆标准化为 \dfrac{x^2}{a^2}+\dfrac{y^2}{b^2}=1 的形式，分为两步：平移、旋转。
-
平移：很简单，先求出新的原点坐标，即 A、B 中点坐标，将所有点减去该点坐标即可。
-
旋转：希望将 A 点旋转到 x 轴负半轴作为左焦点，B 点旋转到 x 轴正半轴作为右焦点。
计算逆时针旋转的角度 \theta，用 2\pi 减去 OB 所在角度即可。
接着，利用旋转矩阵：
R(\theta)=\begin{bmatrix}
\cos\theta & -\sin\theta\\
\sin\theta & \cos\theta
\end{bmatrix}
对每个点作旋转变换即可。
\begin{bmatrix}
x'\\
y'
\end{bmatrix}
=\begin{bmatrix}
\cos\theta & -\sin\theta\\
\sin\theta & \cos\theta
\end{bmatrix}
\begin{bmatrix}
x\\
y
\end{bmatrix}=
\begin{bmatrix}
x\cos\theta - y\sin\theta\\
x\sin\theta+y\cos\theta
\end{bmatrix}
数值积分
将交集区域的面积近似为多个小矩形的面积之和，对于每个 x 值 (-a\le x\le a)，需要求出竖直线与椭圆相交的区间和与三角形相交的区间，取两个区间的交，作为小矩形的高。
- 与椭圆相交的区间为 \left[-b\sqrt{1-\dfrac{x^2}{b^2}}, b\sqrt{1-\dfrac{x^2}{b^2}}\right]。
- 与三角形相交的区间，可以用如下方式求得：
- 若三个顶点分布在竖直线左右两侧，那么有相交，否则无相交。
- 有相交时，不妨假设左侧有一点，右侧有两点，那么竖直线与三角形交于左侧一点与右侧两点的两条连线上，分别计算交点即可。
精度问题
### 代码实现
```cpp
#include<bits/stdc++.h>
using namespace std;
constexpr double PI = 3.14159265358979323;
void solve(){
double xA, yA, xB, yB, L; cin >> xA >> yA >> xB >> yB >> L;
vector<double>tx(3), ty(3);
for(int i = 0; i < 3; i++) cin >> tx[i] >> ty[i];
// 整体平移
double xO = (xA + xB) / 2, yO = (yA + yB) / 2;
auto translate = [&](double &x, double &y){ x -= xO, y -= yO; };
translate(xA, yA);
translate(xB, yB);
for(int i = 0; i < 3; i++) translate(tx[i], ty[i]);
// 获取旋转角 theta
double xOB = atan2(yB, xB);
if(xOB < 0) xOB += 2 * PI;
double theta = 2 * PI - xOB;
// 整体旋转
// cout << theta / PI * 180;
auto rotate = [&](double &x, double &y){
auto u = x, v = y;
x = u * cos(theta) - v * sin(theta);
y = u * sin(theta) + v * cos(theta);
};
rotate(xA, yA);
rotate(xB, yB);
for(int i = 0; i < 3; i++) rotate(tx[i], ty[i]);
// 椭圆半长轴a, 半短轴b
double a = L / 2, b = sqrt(a * a - xA * xA);
// 获取直线与三角形相交的区间
auto get_seg = [&](double x) -> pair<double, double>{
vector<pair<double, double>>l, r;
for(int i = 0; i < 3; i++){
if(tx[i] < x) l.emplace_back(tx[i], ty[i]);
else r.emplace_back(tx[i], ty[i]);
}
if(l.size() && r.size()){
if(l.size() == 2) swap(l, r);
double segl = l[0].second + (r[0].second - l[0].second) * (x - l[0].first) / (r[0].first - l[0].first);
double segh = l[0].second + (r[1].second - l[0].second) * (x - l[0].first) / (r[1].first - l[0].first);
if(segl > segh) swap(segl, segh);
return {segl, segh};
}
return {0, 0};
};
double res = 0;
constexpr double dx = 0.0001;
// 开始积分
for(double x = -a; x <= a; x += dx){
double y = b * sqrt(1 - x * x / a / a);
auto [l, r] = get_seg(x);
double low = max(l, -y), high = min(r, y);
res += max(.0, high - low) * dx;
}
cout << fixed << setprecision(2);
cout << res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
```