主題

ZeroJudge - a042: 平面圓形切割 解題心得

Not In My Back Yard | 2021-01-10 00:00:08

題目連結:


題目大意:
輸入有多列,每列給定一正整數 n,代表總共有 n 個圓。試問:大小任意的 n 個圓任意放置於座標平面上,最多可以將平面切割成幾個區域?



範例輸入:
3
4


範例輸出:
8
14


解題思維:
首先,只有一個圓的時候,會將平面切成 2 塊(即圓內、圓外);
兩個圓時會將區域,最多會將平面切成 4 塊;
三個圓,最多可以切 8 塊……

可以觀察到區域數的增長為
2 + (2 + 4 + 6 + …… + 2(n - 1))
因為每個圓如果都可以與先前放的圓都各自交於兩點,則切出來的區域最多。假設現在是放第 n 個圓,則該圓可以與先前的 n - 1 個圓都各自交於兩點。因此第 n 個圓的圓周上會有 2(n - 1) 個點即代表該圓新切出了 2(n - 1) 個區域。

所以我們可以簡化上式
2 + 2(1 + 2 + 3 + …… + (n - 1))
套用等差級數公式得
2 + 2(n(n - 1) ÷ 2)
因此得公式
n ^ 2 - n + 2




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
50 巴幣: 0

創作回應

相關創作

更多創作