作者bleed1979 (十三)
站内Prob_Solve
标题Re: [请益] SPOJ9 DIRVS
时间Sat Nov 27 09:04:17 2010
抱歉再利用一篇文章解释这题模糊不清的地方。
题目网址：
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