PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [請益] SPOJ9 DIRVS

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間14年前 (2010/11/27 09:04)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/3 (看更多)

抱歉再利用一篇文章解釋這題模糊不清的地方。題目網址：http://www.spoj.pl/problems/DIRVS/ 對於題目規定的direct visibility，我粗淺的了解如下：目標點(i1, j1)，測試點(i2, j2)，現在只討論i1 != i2 && j1 != j2的平面兩點，兩點的2D連線為兩sqare中心點彼此的連線，故連線距離有以下的公式： double calDistance(double y1, double x1, double y2, double x2) { return sqrt((y1 - y2) * (y1 - y2) + (x1 - x2) * (x1 - x2)); } 兩點的直線距離代入公式(在此先使用原始算法，不簡化同加0.5的可省略)： calDistance(i1 + 0.5, j1 + 0.5, i2 + 0.5, j2 + 0.5); 目標點(i1, j1)的高度為2，測試點(i2, j2)的高度為4。分別標記為h[i1][j1], h[i2][j2]，以目標點為基準點得到3D高度的斜率mh，則有如下的推導： (請注意題目有句half metre above surface，在表面上半公尺，高度也要加0.5) mh = (double)((h[i2][j2] + 0.5) - (h[i1][j1] + 0.5)) / calDistance(i1 + 0.5, j1 + 0.5, i2 + 0.5, j2 + 0.5); 則對於目標點和測試點之間經過的cube，平面座標記為(ip, jp)，如果是取cube中心點來計算，同斜率mh該有的高度hp應該為： (將mh的計算移項推導出來) hp = mh * calDistance(i1 + 0.5, j1 + 0.5, ip + 0.5, jp + 0.5) + (h[i1][j1] + 0.5); 如果h[ip][jp] > hp，則表示被檔到視線。 ####這邊是疑點1.， ####計算是metre above the surface，但擋住視線必須是cube的solid。這是由經過的cube的中心點計算的，但實際上這視線在3D是以斜線呈現的，所以上述推導hp的公式如果在平面不是經過(ip, jp)中心點就不能計算中心點，如果在(i1 + 0.5, j1 + 0.5)和(i2 + 0.5, j2 + 0.5)的2D連線交於 (ip, jp)的點記為(it, jt)，則公式要修正： hp = mh * calDistance(i1 + 0.5, j1 + 0.5, it, jt) + (h[i1][j1] + 0.5); 以上是我判斷direct visibility的基本認知和公式。問題就在於如何快速的(it, jt)的計算。以 row 1 column 5 高度 2 3 4 1 5 從(1, 1)到(1, 3)，套入上面的公式。兩點距離基準點(1, 1)的calDistance(1.5, 1.5, 1.5, 3.5) = 2.0 mh = (4.5 - 2.5) / 2.0 = 1.0 我們看高度為3的點(1, 2)，這條視線在左邊交於點(1, 2)假設是(1.5, 2.0001)，最遠的範圍(1.5, 2.9999)。則利用公式計算左邊高度應該為3.5001，最遠高度應為4.4999。 (以上是假設誤差在0.0001，實際上誤差是無窮小的) 3.5001 > 3.0 && 4.4999 > 3.0 故這視線不會被檔到。目前問題是1維的很簡單，但平面是有難度的。下面是一個2D的square。 column 2.0 3.0 row 1.0 -------- | | | | | | 2.0 -------- 將上圖的要討論的點標記在下圖： (1.0, 2.0) (1.0, 3.0) *--------* | | (1.5, 2.0001)|* | | *|(1.6666, 2.9999) *--------* (2.0, 2.0) (2.0, 3.0) 對於從(1.5, 2.0001)左方穿過square直到(1.6666, 2.9999)的右方的我的計算方法： #deifne LEFT (1 << 0) #define RIGHT (1 << 1) #define UP (1 << 2) #define DOWN (1 << 3) char touch[205][205]; // 初始化全為0 直線公式 y = mx + b，m和b已經計算出，則x帶入2.0可得y = 1.49999，取整數為1 touch[1][2] |= LEFT; 則x帶入3.0可得y = 1.66665，取整數為1 touch[1][2] |= RIGHT; // 3 - 1 = 2 同理UP和DOWN，我的想法在touch[1][2]有兩個以上的標記，就可以判斷點(1, 2)是被穿過的。但是也有一個可能是直線從(1.0, 2.0)穿過(2.0, 3.0) 完全沒有標記但有被穿過，或是(1.0, 2.0)穿過(1.66666, 2.99999)，此時只有RIGHT標記但有被穿過，所以我又多計算x帶入2.5，得y = 1.59999，只要y是有小數點的，就表示是被穿過的。如此兩道工序來快速判斷(it, jt)，時間上是允許的，但是WA，唉，可能還需要多debug，就請觀文者給予指導。對於上面標註的#####疑點，不曉得觀文者有沒有看法。謝謝。 Bleed -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.43.120.234