UVa 1447 - Malfatti Circles

链接

传送门

题意

给出三角形的三个顶点坐标,求三个Malfatti Circle的半径。

思路

参考维基百科中对Malfatti Circle的介绍,其半径公式为:

$$r_1 = \frac{r}{2 \left(s - a\right)} \left( s + d - r - e - f \right)$$

式中$s$为三角形的周长,$d$、$e$、$f$分别为$A$、$B$、$C$三个顶点到三角形内心的距离。其余两个Malfatti Circle的半径计算与之同理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct Point {
double x, y;
Point() {}
Point(double x, double y): x(x), y(y) {}
} A, B, C;
typedef Point Vector;
Vector operator - (const Point& a, const Point& b) {
return Vector(a.x - b.x, a.y - b.y);
}
double Dot(const Point& a, const Point& b) {
return a.x * b.x + a.y * b.y;
}
double Cross(const Point& a, const Point& b) {
return a.x * b.y - a.y * b.x;
}
double Length(const Vector& a) {
return sqrt(Dot(a, a));
}
int main() {
while (~scanf("%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y) && (A.x || A.y || B.x || B.y || C.x ||C.y)) {
double a = Length(B - C);
double b = Length(C - A);
double c = Length(A - B);
Point O;
O.x = (a * A.x + b * B.x + c * C.x) / (a + b + c);
O.y = (a * A.y + b * B.y + c * C.y) / (a + b + c);
double s = (a + b + c) / 2, r = fabs(Cross(B - A, C - A)) / (a + b + c);
double d = Length(A - O), e = Length(B - O), f = Length(C - O);
double ra = r / 2 / (s - a) * (s + d - r - e - f);
double rb = r / 2 / (s - b) * (s + e - r - d - f);
double rc = r / 2 / (s - c) * (s + f - r - d - e);
printf("%.6f %.6f %.6f\n", ra, rb, rc);
}
return 0;
}

支付宝扫码领红包