2013年3月26日 星期二

[UVA] 143 Orchard Trees

給一個三角形,求出在其內的格點(整數座標)個數。
這一題我是用scan line。從y = 1 掃到 y = 99. 每次scan時,計算scan line和三角形的三個邊的交會點。如果有的話,把交點依x排序,對min 取ceiling (left), max 取 floor (right):
於是  right - left  + 1 即為該條scan line 上貢獻的格點數。累加即可。

這一題的陷阱有:
1. floating precision. 把 double 換成long double

2.  c++ 的ceil 和 floor不夠準。要用
    left = ceil( min - EPS)
    right = floor(max + EPS)
   
    其中正 負的的order自己想想

3. 只計算  1 <= x <= 99, 1<= y <= 99的格點,所以其實left跟right和要做處理:
    left = max(1, left)
    right = min(99, right)
    而且只考慮 right >= left的情況

Test case
input

5.0 31.9 3.5 63.4 66.5 46.6
1 1 1 1 1.1 1.1
99.00001 99.00001 99.99999 99.99999 99.99999 99.99999
1.5 1.5  1.5 6.8  6.8 1.5
10.7 6.9  8.5 1.5  14.5 1.5
71.67 88.3 45.02 49.09 98.49 0.1
5 3 7 1 3 1
3 3 3 3 3 3
1 1 50 1 100 1.01
1 1 100 1.01 1 1.01
0 1 4 1 2 3
0 0 4 0 2 2
0 0 0 0 0 0

output (blogger的indent沒做好,請自行調整)

743
    1
   0
  15
  17
1701
   9
   0
  50
   1
   8
   4

沒有留言:

張貼留言