uva 10382 - Watering Grass
問題(Question):
一直 Wrong Answer ,不知道錯在哪
題目和 udebug 的測資都有過
程式碼(Code):(請善用置底文網頁, 記得排版)
https://paste.ofcode.org/Gb7qp84QkYbRMuFz82Qi2e
補充說明(Supplement):
目前做過的努力:
檢查了 長寬為零的情況、重覆的圓
double 精度 ( uDebug 測資有 1 10000001 1
10000000 10000000)
做法/解釋:
1. 讀入測資,邊讀邊把圓形換算成長方形的邊長一半
(即中心點向左或向右可以遮住多長的長度) 存入 extlen
p.s 處理畢式定理時怕精度不夠所以 w2 (寬度平方)
先平方再除 4.0
2. l 為草地長度,每次都從最右邊開始遮掉,每遮掉一次
就縮小草地的長度,即 l 一直變小,直到小於 0
3. 計算每個圓 (如果可以蓋注草地最右邊的邊緣的話) 可
以遮掉多少面積 (長度) ,並把這個資訊存入 ecr
(Effective coverage of right end) 每次都選 ecr
值最大的的圓來遮。
4. 若 l<=0 即達成全部遮住的目標;
若 l>0 且 ecr 都為零即代表無法完全遮住草地