题解：P10410 「QFOI R2」寺秋山霭苍苍
lsrsrl
·
·
题解
题目传送门
前言
我是用的是高中方法。
前置知识
勾股定理
### 海伦公式
若三角形三边长为 $a,b,c$，设半周长 $p=\frac{a+b+c}{2}$，则三角形面积为 $S=\sqrt{p(p-a)(p-b)(p-c)}$。
### 定比分点
若有两点 $A(x_1,y_1),B(x_2,y_2)$，让求一点 $P(x,y)$ 使得 $\frac{AP}{PB}=k$，则 $x=\frac{1}{k+1} \times x_1 + \frac{k}{k+1} \times x_2$，$y=\frac{1}{k+1} \times y_1 + \frac{k}{k+1} \times y_2$。
## 思路
枚举 $p$，因为误差不到 $10^{-4}$ 就算对，所以我们可以每次枚举 $p$ 增加 $10^{-6}$，注意题目的 $0 \le l,r \le 1$，不会超时。（也可以每次枚举$p$增加更少。)
对于每个 $p$，先用定比分点算出每个点的坐标，再用勾股定理算出每两个点的个距离，最后用海伦公式算出面积。
## 注意
我给的定比分点不能直接计算本题，需要一点分析：
$\frac{AF}{AB}=k$ 能推出 $AD:DB=k:1-k$，设 $A(x_1,y_1),B(x_2,y_2)$，则由定比分点，$F(kx_2+(1-k)x_1,ky_2+(1-k)y_1)$，这样才能解出这道题。
## AC code
```cpp
#include <bits/stdc++.h>
const double eps = 1e-6//eps是误差，此题误差不到1e-4就算对，所以每次+1e-6就能过
using namespace std;
double ans = 1e9;
double gou_gu(double x1, double y1, double x2, double y2) {//勾股定理
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double hai_lun(double x, double y, double z) {//海伦公式，x,y,z为长度
double p = (x + y + z) / 2;
return sqrt(p * (p - x) * (p - y) * (p - z));
}
int main() {
double l, r, x1, y1, x2, y2, x3, y3;//如果定义为全局变量会报错
cin >> l>> r>> x1>> y1>> x2>> y2>> x3>> y3;
for (double p = l; p <= r; p += eps) {
double x_1 = p * x2 + (1 - p) * x1, y_1 = p * y2 + (1 - p) * y1;
double x_2 = p * x3 + (1 - p) * x2, y_2 = p * y3 + (1 - p) * y2;
double x_3 = p * x1 + (1 - p) * x3, y_3 = p * y1 + (1 - p) * y3;//上面推导的公式
double a = gou_gu(x_1, y_1, x_2, y_2);
double b = gou_gu(x_2, y_2, x_3, y_3);
double c = gou_gu(x_3, y_3, x_1, y_1);
ans = min(ans, hai_lun(a, b, c));//输出让我们输出最小就取最小值
}
cout << fixed << setprecision(12)<< ans;//setprecision里的数可以是其他的（注意精度）
return 0;
}
```
[AC记录](https://www.luogu.com.cn/record/245169924)。