※ 引述《derekhsu (華麗的天下無雙)》之銘言： : 第三題的話就真的難倒我了，我知道方向，也知道是計算洞（蒼蠅可以閃過 : 拍子的面積/拍子的面積），但怎麼去計算邊緣的那些不完整的方形.... : 完全不知道，就請高手解答囉。 不完整的方形: 每個洞都是一個方形和圓形的intersection 在題目的配置下 如果有intersect的話一定會交在兩個點 這兩個點用一條chord連起來 會把洞切成一個半月形和一個多邊形 半月形的面積=這段弧對應的圓心角張開的面積-圓心角張開的等腰三角形的面積 多邊形看是梯形, 還是三角形, 還是方形缺一角的五角形 這題我也花了靠腰久. 我看到他limits只有t<R, f<R, r<R 最多兩千條string, 以為會有很多很time comsuming的case 就像作ACM的時候就偶而常遇到莫名其妙time exceeded的類型; 於是考慮了一堆extreme case的估計, 把非常dense和非常sparse的狀況釐出來 最後沒能在時限前debug完...... 結果沒想到在, 時限前的半小時改弦更張, 很暴力 ( O( (R/(g+2r))^2 ) )的, 假設球拍中心的的方式(0, 0), 半邊有n條弦的話, 把每個方格依照 (0, 0) -> (0, 1) -> (0, 2) ...-> (0, n) -> (1, 0) -> (1, 1) -> (1, 2) ...-> (0, m) (m是過了這格以後 就整個格子都在 圓外) ->...這樣一路算下去 喵的, 時間到之後沒多久就寫完了且完全正確 早知道就這樣寫, 頂多花四五十分鐘...... 事實證明GCJ的test case沒那麼刁難(?) 而且我也沒有估計好暴力法到底會花多少 執行時間. Qualification round很有練習效果. 先前作他過去的practice就缺 少臨場感和緊張感 XD --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.136.227.171