计算几何(直线交点) - Morley‘s Theorem - UVA 11178

计算几何(直线交点) - Morley’s Theorem - UVA 11178

题意：

$给定三角形ABC三个顶点A、B、C的坐标，如上图$

$求出三个角的三等分线的交点构成的△DEF的三个顶点D、E、F的坐标。$

输入：

$T组测试数据，$

$每组测试数据包括六个整数，依次为A、B、C三个顶点的横纵坐标。$

输出：

$六个浮点数，依次表示D、E、F的横纵坐标。$

Sample Input

2 1 1 2 2 1 2 0 0 100 0 50 50

Sample Output

1.316987 1.816987 1.183013 1.683013 1.366025 1.633975 56.698730 25.000000 43.301270 25.000000 50.000000 13.397460

---

分析：

莫利定理（Morley’s theorem），也称为莫雷角三分线定理。将三角形的三个内角三等分，靠近某边的两条三分角线相交得到一个交点，则这样的三个交点可以构成一个正三角形。这个三角形常被称作莫利正三角形。

$先根据A、B、C三个顶点的坐标，计算出三个角的大小，接着得到角的三等分线对应的向量，$

$根据这些向量计算出对应的交点坐标。$

代码：

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <fstream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; const double eps = 1e-10; const double pi = acos(-1.0); struct Point { double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} }; int dcmp(double x) { if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } //点与向量 typedef Point Vector; Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } Vector operator - (Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); } Vector operator * (Vector A, double p) { return Vector(A.x * p, A.y * p); } Vector operator / (Vector A, double p) { return Vector(A.x / p, A.y / p); } bool operator < (const Point& a, const Point& b) { return a.x < b.x || (!dcmp(a.x - b.x) && a.y < b.y); } bool operator == (const Point& a, const Point& b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; } double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; } double Length(Vector A) { return sqrt(Dot(A, A)); } double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); } //A和B夹角 double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; } //若A到B逆时针则为正，否则为负 double Area2(Point A, Point B, Point C) { return Cross(B - A, C - A); } //三角形ABC的面积的两倍(有方向) double angle(Vector v) { return atan2(v.y, v.x); } //arctan(y/x) double dis2(Point A, Point B) { return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y); } Vector Rotate(Vector A, double rad) //向量A逆时针旋转rad度 { return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad)); } Point GetLineIntersection(Point P, Vector v, Point Q, Vector w) //求过点P的向量v方向上的直线与过点Q的向量w上的直线的交点 { Vector u = P - Q; double t = Cross(w, u) / Cross(v, w); return P + v * t; } int T; Point A, B, C; int main() { scanf("%d", &T); while (T--) { scanf("%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y); Vector AB = B - A, AC = C - A, BC = C - B; double angA = Angle(AB, AC), angB = Angle(A - B, BC), angC = Angle(A - C, B - C); Vector A1 = Rotate(AB, 1.0 / 3 * angA), A2 = Rotate(AB, 2.0 / 3 * angA), B1 = Rotate(BC, 1.0 / 3 * angB), B2 = Rotate(BC, 2.0 / 3 * angB), C1 = Rotate(A - C, 1.0 / 3 * angC), C2 = Rotate(A - C, 2.0 / 3 * angC); Point F = GetLineIntersection(A, A1, B, B2), E = GetLineIntersection(A, A2, C, C1), D = GetLineIntersection(B, B1, C, C2); printf("%lf %lf %lf %lf %lf %lf\n", D.x, D.y, E.x, E.y, F.x, F.y); } return 0; }