Question

求一算法 ,是关于数组的问题

如题
一个坐标图储存着若干黑点,其它都是白点
求左右上下方向上都有黑点的白点个数
这些点坐标范围[-10亿,+10亿]
黑点个数[0,10万]

Answer 1

1、将所有黑点坐标值离散化。
2、将黑点数据处理为两份：
A、将同列的点连成小线段，即同列中相邻的点连成线段，线段除两个端点外中间不存在黑点，线段可用C(y1,y2,x)表示，其中y1<y2，并按y1值排序。
B、将同行的点连成大线段，即只需将同行中两个最远点相连，其余点均包含在该线段中，线段可用R(x1,x2,y)表示，其中x1<x2，并按y值排序。
3、按y值从小到大逐一处理行大线段，过程中需要两个数据结构：
树状数组ta：ta[x]表示与当前行线段所在直线相交并且两端点不在直线上的列线段数量。
优先队列qu：队列中存放列线段，以y2值小为优先。
另需记录满足条件的白点数的变量cnt，然后，对于每条行线段具体处理步骤：
1）将待处理的列线段中所有满足Cj.y1<Ri.y的列线段入队qu，并且ta[Cj.x]加1。
2）将qu中所有满足Ck.y2<=Ri.y的列线段从qu出队，并且ta[Ck.x]减1。
3）cnt+=树状数组ta中Ri.x1+1到Ri.x2-1的和，即与当前行线段相交的列线段数。
4、处理完所有行线段后cnt即答案。
优先队列的出队和入队都是O(logn)，树状数组的数组元素加减和数组求和也都是O(logn)，具体原理这里就不说了。虽然在处理每条行线段时可能会进行多次列线段的出入队操作，但从全局来看，每条列线段仅会出入队列各一次。
这是我的思路，没有经过代码实践，有问题可再讨论^_^。

追问

你只判断了Cj.y1<Ri.y<Cj.y2
没有判断是否Ri.x1 < Cj.x < Ri.x2是否也成立
我现在有其它方法解决交点是黑点的情况
你只要给出能判断上面两式都成立的i,j有多少组的算法即可

追答

Ri.x1 < Cj.x < Ri.x2无需特殊判断，树状数组求和的时候求Ri.x1+1到Ri.x2-1的和啊，就是(Ri.x1,Ri.x2)这个区间内的列线段数量。

追问

还有点问题
不能根据x开出ta ,这个数组太大
但根据j开ta的话,还是要判断R.x1<Cj.x<Ri.x2
而且刚刚的测试生成ta用了5s
这是acm的题还是过不了

追答

我想说的是你真的有按照我说的算法来做吗？
1、将所有黑点坐标值离散化。

这里就解决了坐标值范围太大的问题，因为你这问题实际上不必关心具体的坐标值，只要他们的相对大小关系不变就可以了啊。

Answer 2

问题：求一算法 ,是关于数组的问题
回答：不存在这样的算法，大伙还是散了吧！
20亿*20亿个点用黑白表示，需要的内存最少为：20亿*20亿/8字节，大约2^31 * 2^31 /8 = 1G * 500M 字节，这是在逗比吗

追问

不是黑点就是白点，而黑点最多10万
struct tagNODE {
int x ；
int y ；
}
表示这个坐标图
只要
struct tagNODE black【100000】；
int black_length ;
只要100000*8+4=800004b<1mb
算了，懒得离你们了，还不如水分的

追答

没仔细看你的题，被你的20亿吓住了。事实上这个题跟你这个20亿一点关系都没有。

不知道你们怎么用了那么长时间，我的就0.083秒。我的机器是i7笔记本。

下面是最坏情况，采用了16万个点。程序可能还有瑕疵，但算法结构就是这样。算法效率还有提高空间，我没有仔细优化。

代码如下：

Answer 3

貌似只能穷举，每个坐标点都取出来，然后找出该点周围的点，进行判断，正确，则计数变量+1。判断语句可以封装到一个函数体中，反复调用。

追问

不能穷举 ,太慢了
穷举没有几个钟不会返回
我到有个10s左右的算法
但还是太慢 ,要个4s左右的算法才行

追答

10s左右的算法是什么样的，可以在上面改进缩短时间么?

追问

把同行或同列的点连成线段，然后判断行列线段是否相交，相交点是否白点，复杂度n^2，需要nlogn型的算法才行

追答

是说黑色点横线段与纵线段连线相交点为白色么？这要怎么实现判断？找出黑色点首先就得遍历了吧？

追问

看题啊,题目肯定给的是黑点的坐标啦,难道把整个坐标图当作输入?
可以不问吗,现在是我提问耶,我要新的算法,我的算法说了不合适

Answer 4

人生的剧场循环上演着曲散人离的戏剧。

追问

我知道,Ulimited Water Works嘛

Answer 5

小学老师走的早····

追问

你想说分别向上下左右找黑点,不就行了吗?
是吧?
你也不看看,20亿*20亿个点,一个一个判断要多久?
有这么简单吗?
我求的是算法!!!