我有以下任务:
In the program we should draw lines on a bit mapped display. An array of
n
pairs of reals(a<sub>i</sub>,b<sub>i</sub>)
defined then
linesy<sub>i</sub> = a<sub>i</sub>*x + b<sub>i</sub>
. The lines were ordered in thex
-interval[0, 1]
in the sense thaty<sub>i</sub> < y<sub>i+1</sub>
for all values ofi
between0
andn-2
and for all values ofx
in[0, 1]
不太正式的是,垂直板中的线条不接触。给分(x,y)
, 其中0 < x < 1
, 我们想确定两条线将点括起来。
我们怎样才能快速解决这个问题?
最佳答案
Function bracket( Real x, Real y, Array a[1..n],b[1..n] of Reals): Returns void
{
Integer i = 1;
While (i<=n && (a[i] * x + b[i]) <= y, i++)
If (i==1 || i == n+1)
{ Print("Not bracket exists");
Exit()
}
If (a[i] * x + b[i]) == y)
{ Print("Point lies on line",i);
Exit()
}
Print("Point between lines ", i-1, " and ", i);
}
但是有一个小问题。见下图:
你会说点 F 被 [0,1]x[0,1] 中的两条线“括起来”了吗?在这种情况下,正确答案是什么?
关于找到包围一个点的线的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3997359/