幾何算法:Morley's Theorem

我記得剛讀高中時(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)練指南》

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末寂恬,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子莱没,更是在濱河造成了極大的恐慌初肉,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件饰躲,死亡現(xiàn)場離奇詭異牙咏,居然都是意外死亡臼隔,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門妄壶,熙熙樓的掌柜王于貴愁眉苦臉地迎上來摔握,“玉大人,你說我怎么就攤上這事丁寄“碧剩” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵伊磺,是天一觀的道長盛正。 經(jīng)常有香客問我,道長奢浑,這世上最難降的妖魔是什么蛮艰? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮雀彼,結(jié)果婚禮上壤蚜,老公的妹妹穿的比我還像新娘。我一直安慰自己徊哑,他們只是感情好袜刷,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著莺丑,像睡著了一般著蟹。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上梢莽,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天萧豆,我揣著相機(jī)與錄音,去河邊找鬼昏名。 笑死涮雷,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的轻局。 我是一名探鬼主播洪鸭,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼仑扑!你這毒婦竟也來了览爵?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬榮一對情侶失蹤镇饮,失蹤者是張志新(化名)和其女友劉穎蜓竹,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡梅肤,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年司蔬,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片姨蝴。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖肺缕,靈堂內(nèi)的尸體忽然破棺而出左医,到底是詐尸還是另有隱情,我是刑警寧澤同木,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布浮梢,位于F島的核電站,受9級(jí)特大地震影響彤路,放射性物質(zhì)發(fā)生泄漏秕硝。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一洲尊、第九天 我趴在偏房一處隱蔽的房頂上張望远豺。 院中可真熱鬧,春花似錦坞嘀、人聲如沸躯护。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽棺滞。三九已至,卻和暖如春矢渊,著一層夾襖步出監(jiān)牢的瞬間继准,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來泰國打工矮男, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留移必,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓昂灵,卻偏偏與公主長得像避凝,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子眨补,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容