关于Algorithms Week3如何满分的问题

明天就要due了，然而楼主的week3还没满分。我遇到的问题是这样的，要处理防止subsegment的出现。我的思路是建一个叫checktable 的Arraylist记录已经存入的linesegment，在进行搜索时，如果发现摸个搜索到的linesegment是和checktable的linesegment共线的话，那么就扔掉这组值。由于我们在搜索之前对points进行了排序，所以可以肯定，相对长的线一定会先出现，而subsegment的情况会在这之后出现。因此，这种方法是可行的，不过当已有的checktable变的很大时，时间就要远远超过N*2logN，所以时间会有两个测试过不了。如果不考虑subsegment的问题，时间测试可以过去，但是correctness样例会有4个过不了。楼主也尝试了不一边搜索一边判断，也就是先N*2logN搜索出一些潜在值，再取筛选这些潜在值当中斜率一样的中相对较长的线。不过写完以后发现这种方法在一些情况下会优化，但是依然过不了要求的时间test。想问问各位同僚和前辈，大家是怎么在时间范围允许内解决subsegment的问题的？

wendaomumu 发表于 2017-1-14 21:44
比如ABCDE五个点共线，可能是相对A比较找到这一组共线，也可能是相对于BCDE做比较时找到这一组共线。在生成 ...

我不确定是否正确理解了层主的回答，不过我的问题是ABCDE五个点，以A为原点，可以找到一条线A到E，以B为原点，其实只会找到B到E，因为此时算出A的斜率是负数，然而 B ->E是A->E的一种子情况，我该怎么避免把B->E加入到我的结果中呢？
我感觉您说的解答问题是针对于如何避免A->E 和 E -> A 会算两次这个问题。不过这个问题我个人认为其实也可以通过仅仅统计所有点的组合而不是排序来避免，也就是说，在做for循环的时候
for （int i = 0 ; i < points.length ; i++）{
for (int j = i+1;j < points.length ;j++)
}
这样相当于A点在算完A->E之后，就被"丢弃“掉了。

我在最开始就按nature order用Arrays.sort()了，这样再按点从大到小来作为基准点，这样找到的线段的较大端点一定是由大到小找到的。这样在找到满足条件的线段时检查这线段上的点，如果有比当前基准点更大的说明这线段就已经建过了。时间内存测试都能过。