※ 引述《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