創作內容

0 GP

ZeroJudge - b288: 夏季大三角 解題心得

作者:Not In My Back Yard│2019-06-11 13:23:55│巴幣:0│人氣:175
題目連結:


題目大意:
給定一正整數 N (N ≦ 1, 000),代表有 N 個點,每個點佔一列輸入。

接著的 N 列,每列給定兩浮點數,代表此點在標準座標平面上的座標。

求從這 N 個點挑出三點可形成最大的三角形之面積為何?



範例輸入:
5
0 0
1 6
2 3
1.5 1.5
5 0


範例輸出:
15.000000


解題思維:
本題暴力硬 A 是可以過的。但是我們也可以採取幾何學的看法——凸包。

根據凸包的定義,即最小的、可包覆所有點的凸多邊形。因此,本題所要求最大的三角形之三頂點必定皆在凸包的頂點(邊)上。因為不在凸包上的話,就可以往外延展碰到凸包,進而形成更大的三角形。

因此,只要找出這 N 個點的凸包,並窮舉其頂點的挑法即可找出最大的三角形。(凸包的找法可以參考之前的文章

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4423684
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|數學|幾何|窮舉

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊切換新版閱覽

作品資料夾

pig102315015大家
鬼眼獵魔師第六章更新,為釐清張可欣為何被盯上,霆傑將其帶往冥界調查,冥界究竟是什麼地方? 歡迎觀賞看更多我要大聲說昨天22:05


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】