题解：P10410 「QFOI R2」寺秋山霭苍苍

前言

我是用的是高中方法。

前置知识

勾股定理。
海伦公式。
定比分点公式。

勾股定理

(x_1,y_1),(x_2,y_2)

之间的距离为

\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}

。

海伦公式

若三角形三边长为

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记录。

题解：P10410 「QFOI R2」寺秋山霭苍苍

文章操作

前言

前置知识

勾股定理

海伦公式

定比分点

思路

注意

AC code

相关推荐

评论

题解：P10410 「QFOI R2」寺秋山霭苍苍