我記得剛讀高中時(shí)，當(dāng)時(shí)應(yīng)該還在軍訓(xùn)，沒有正式上課蚜印。晚自習(xí)的時(shí)候敷搪，數(shù)學(xué)老師出了幾道難度頗大的平面幾何題兴想，其中一題是證明Morley's Theorem：做三角形ABC每個(gè)內(nèi)角的三等分線，相交成三角形DEF赡勘，則DEF是等邊三角形嫂便。如圖：
UVa利用這個(gè)定理出了這樣一道題：根據(jù)ABC的頂點(diǎn)坐標(biāo)來計(jì)算DEF的頂點(diǎn)坐標(biāo)（需要逆時(shí)針輸入頂點(diǎn)坐標(biāo)）。
這道題目沒有用到什么算法闸与，只需要根據(jù)題意計(jì)算毙替。根據(jù)向量的基本計(jì)算，可以求出ABC的邊的向量以及內(nèi)角践樱，然后旋轉(zhuǎn)1/3的內(nèi)角就可以得到三等分線的向量厂画，再去計(jì)算直線的交點(diǎn)。
關(guān)于基礎(chǔ)計(jì)算的代碼拷邢，在上篇文章中都已給出袱院，這里直接切入問題內(nèi)核。
···
class Morley {
static Point getPoint(Point a, Point b, Point c) {
Vector v1 = c.substract(b);
double rad1 = Vector.angle(a.substract(b), v1);
v1 = Vector.rotate(v1, rad1 / 3);
Vector v2 = b.substract(c);
double rad2 = Vector.angle(a.substract(c), v2);
v2 = Vector.rotate(v2, -rad2 / 3); // 負(fù)數(shù)表示順時(shí)針旋轉(zhuǎn)
return Vector.getLineIntersection(b, v1, c, v2);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine(); // 過濾掉\n
while (n-- > 0) {
String str = in.nextLine();
List<Double> list = Stream.of(str.split("\\s+")).map(Double::parseDouble).collect(Collectors.toList());
System.out.println(list);
Point a = create(list.get(0), list.get(1));
Point b = create(list.get(2), list.get(3));
Point c = create(list.get(4), list.get(5));
Point d = getPoint(a, b, c);
Point e = getPoint(b, c, a);
Point f = getPoint(c, a, b);
System.out.printf("%f %f %f %f %f %f\n", d.x, d.y, e.x, e.y, f.x, f.y);
}
}
}
···
算法充分利用了定理的對稱性解孙，既可以減少思考坑填，又可以復(fù)用代碼。
測試數(shù)據(jù)（親測無誤）：
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
還是回到十幾年前的那個(gè)晚上弛姜，我無法證明這道難題脐瑰，但是卻覺得數(shù)學(xué)非常神奇。隨后我就忘了這道題廷臼。等我上了大學(xué)苍在，在圖書館中才無意間看到了這道題目的證明，也想起了當(dāng)年的那位老師荠商。
參考：《算法競賽入門經(jīng)典訓(xùn)練指南》
