Lift the Slate (ZOJ Problem Set - 3552)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3552

問題

半径Rの円盤に半径rのドリルでn個の穴を開ける。重心を求めよ。
0

解法

穴がかぶることが無ければ普通に重心の公式で求めれば良い。穴がかぶってしまうので穴の形を考えて厳密に面積とその重心を求めなければならない。穴の形は一番外側の円弧の集合で表記する。これは各円ごとに他の円との交点を求め、それを角度順にソートして他の円の内側になってない部分を求めれば良い。穴の面積と重心はそれぞれの円弧を積分することによって求めることが可能。実際円弧の方程式は $(x-a)^2+(y-b)^2=r^2$ なので変形して積分すると $y=\int_l^r \left( b \pm \sqrt{r-(x-a)^2}\right)dx$ となる。同様に重心は $y=\int_l^r \left(x\left( b \pm \sqrt{r-(x-a)^2}\right) \right)dx$ となる。これらの式をWolframAlphaとかで求めて、全ての円弧の和を適切に取れば計算できる。