363. Bézier Curves http://projecteuler.net/problem=363 所謂的 cubic Bézier curve (三次貝茲曲線) 是由四點個 P0, P1, P2 和 P3 定義的。 這個曲線是這樣被定義的： 分別在線段 P0P1, P1P2, P2P3 上取點 Q0, Q1, Q2 使得 P0Q0/P0P1 = P1Q1/P1P2 = P2Q2/P2P3 = t； 分別在線段 Q0Q1, Q1Q2 上取點 R0, R1 使得 Q0R0/Q0Q1 = Q1R1/Q1Q2 = t； 在線段 R0R1 上取點 B 使得 R0B /R0R1 = t。 當 Q0 在線段 P0P1 上移動時(即當 t 取遍 0 到 1 的所有實數時)， B 所經過的軌跡即為由 P0, P1, P2, P3 定義的貝茲曲線。 網頁中的 Applet 可以讓你拖動 P0, P1, P2, P3 及 Q0 的位置來更加了解其構成。 容易得知這樣子得到的曲線會和線段 P0P1 切於 P0, 和線段 P2P3 切於 P3。 考慮由 P0 = (1,0), P1 = (1,v), P2 = (v,1), P3 = (0,1) 定義的貝茲曲線 來近似一個 1/4 圓弧。 v 的值選得讓這個曲線和 OP0, OP3 兩個直線所圍成的面積為π/4 (即 1/4 單位圓面積)。 問這曲線的長度相對於一個 1/4 圓弧多了多少百分點？ 也就是說，若 L 為這樣的曲線長度，求 100 * (L - π/2) / (π/2)。 答案四捨五入到小數點第十位。 -- 連續兩週難題所以這一週是很數學的題目 XD (我只搶到第 66 名, 前 50 都沒進... u 大倒是進了第 25) 基本上這正是現在一些地方 (例如 Flash) 裡面使用貝茲曲線近似圓的方式 (之所以是近似是因為圓無法分段用貝茲曲線描述) 在那裡一個圓會被描述成由像這樣的四條 1/4「圓弧」所組成的 不過當你求出答案之後就會發現面積相等時長度差其實非常微小 因此在我們看起來它就和一個 1/4 圓弧沒什麼兩樣 除非放到非常大的地方時才會感覺有差異 而這樣做有計算上的好處 在畫圓時的參數式不是 sin 和 cos 而是一個三次多項式 (這個多項式正是這種貝茲曲線被稱做「三次貝茲曲線」的原因 在計算這題時因為要求弧長所以必須求出來 就不多說了) 在計算時間和準確度上能夠更好 同樣的可以定義其他次數的貝茲曲線 原題目裡的 R0 和 R1 的軌跡正各是一個二次貝茲曲線 話說回來, 其實平常在用的近似圓的貝茲曲線不是題目這一條 而是讓曲線中點在圓上的那一條 (v = 4(√2 - 1)/3) 這個面積多了約萬分之三 長度多了約萬分之一點五 但是計算比題目這一條方便多了 -- 話說 362 題的文章怎麼消失了 0.0? -- いああオレたちには見えてるモノがあるbデ きっと誰にも奪われないモノがあるはずさ け 開口一番一虚一実跳梁跋扈形影相弔yュL羊頭狗肉東奔西走国士無双南柯之夢 歪も ぶ 　意味がないと思えるコトがある ラPきっとでも意図はそこに必ずある んの く 依依恋恋空前絶後疾風怒濤有無相生 ラH急転直下物情騷然愚者一得相思相愛 だが ろ 無意味じゃない ラ6あの意図が 恋た で 有為転変死生有命蒼天已死黄天當立 !!6五里霧中解散宣言千錯万綜則天去私 のり --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.91 ※ 編輯: LPH66 來自: 140.112.28.91 (12/19 08:07)