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的半径计算与之同理。

代码

#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;
}