「QFOI R2」寺秋山霭苍苍 官方题解

· · 题解

考查内容：

本文将介绍两种较为简单的方法。

方法一

容易由海伦公式计算出 S_{\triangle\textrm{ABC}}。

根据三角形面积公式 S=\frac{1}{2}ah，\triangle\textrm{AFC} 与 \triangle\textrm{ABC} 有相同的高，且底边长度之比 \frac{|\textrm{AF}|}{|\textrm{AB}|}=p，因此 \frac{S_{\triangle\textrm{AFC}}}{S_{\triangle\textrm{ABC}}}=p。同理，\frac{S_{\triangle\textrm{AFE}}}{S_{\triangle\textrm{AFC}}}=1-p，即得 S_{\triangle\textrm{AFE}}=p(1-p)S_{\triangle\textrm{ABC}}。同理可证 S_{\triangle\textrm{AFE}}=S_{\triangle\textrm{FBD}}=S_{\triangle\textrm{EDC}}=p(1-p)S_{\triangle\textrm{ABC}}。

用割补法可以得到 S_{\triangle\textrm{DEF}}=S_{\triangle\textrm{ABC}}-3p(1-p)S_{\triangle\textrm{ABC}}。至此，初中几何部分结束。

注意到 S_{\triangle\textrm{DEF}} 是关于 p 的开口向上的二次函数，对称轴为 p=\frac{1}{2}。因此，若 l\le\frac{1}{2}\le r，取 p=\frac{1}{2} 最优；否则取 p 为更靠近 \frac{1}{2} 的区间端点最优。至此，初中代数部分结束。

inline double calc(double S, double p) {
    return S - 3.0 * (S * p * (1.0 - p));
}

double l, r, x1, y1, x2, y2, x3, y3;
cin >> l >> r >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
double a = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
double b = sqrt((x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3));
double c = sqrt((x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3));
double p = (a + b + c) * 0.5;
double S = sqrt(p * (p - a) * (p - b) * (p - c));
double k = 0.5;
k = min(k, r);
k = max(k, l);
cout << fixed << setprecision(12) << calc(S, k) << endl;

方法二

令 p 以一定的精度遍历 [l,r]，也就是说枚举 p=l+k\Delta p\le r（k 为非负整数），使用定比分点公式计算出 \textrm{D},\textrm{E},\textrm{F} 的坐标，使用海伦公式计算出 S_{\triangle\textrm{DEF}}，再取得到的所有结果中最小的。

根据方法一中的证明，精度 \Delta p 取 0.01 就足以通过本题，取 10^{-6} 等其他精度也可。

const double eps = 1e-9;

inline double calc(double x1, double y1, double x2, double y2, double x3, double y3) {
    double a = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    double b = sqrt((x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3));
    double c = sqrt((x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3));
    double p = (a + b + c) * 0.5;
    double S = sqrt(p * (p - a) * (p - b) * (p - c));
    return S;
}

double l, r, x1, y1, x2, y2, x3, y3;
cin >> l >> r >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
double S = 1e100;
for(double k = l; k <= r + eps; k += 0.01) {
    double x4 = x1 + (x2 - x1) * k;
    double y4 = y1 + (y2 - y1) * k;
    double x5 = x2 + (x3 - x2) * k;
    double y5 = y2 + (y3 - y2) * k;
    double x6 = x3 + (x1 - x3) * k;
    double y6 = y3 + (y1 - y3) * k;
    chkmin(S, calc(x4, y4, x5, y5, x6, y6));
}
cout << fixed << setprecision(12) << S << endl;