k*j
发帖数: 153 | 1 Given a two dimensional graph with points on it, find a line which passes
the most number of points.
这是在cracking coding interview书里（10.6）的一题。书里是用hash的方法。
public int hashCode(){
int s1= (int)(slope*1000);
int in = (int)(intercept*1000);
return s1 | in;
}
但我一直不明白，如果是x = x1,也就是slope = infinite的情况，如何求这个
hashcode呢？因为infite是inf, 乘上1000 ＝ ？ | k*j
发帖数: 153 | | b*******8
发帖数: 37364 | 3 对斜率无穷的竖线，大不了专门扫一次特殊处理，O（N)时间。 | P**********c
发帖数: 3417 | 4 斜率无穷的直线，书上没有把slope存成无穷，初始值是多少就是多少, Java里应该是
默认为0。你要是用C++写的话，可以在Line的constructor里面的else{}部分把slope设
成0就没问题了.
【在 k*j 的大作中提到】
: Given a two dimensional graph with points on it, find a line which passes
: the most number of points.
: 这是在cracking coding interview书里（10.6）的一题。书里是用hash的方法。
: public int hashCode(){
: int s1= (int)(slope*1000);
: int in = (int)(intercept*1000);
: return s1 | in;
: }
: 但我一直不明白，如果是x = x1,也就是slope = infinite的情况，如何求这个
: hashcode呢？因为infite是inf, 乘上1000 ＝ ？
| l***i
发帖数: 1309 | 5 You have at most (n choose 2)=n^2 lines for each pair of points. Represent
each line as A*x+B*y=C.
Now sort the triples for all lines. Lines coincide will have same (A,B,C) so
count them. This is O(n^2logn). If you have a magic hash function, you can
get O(n^2) assume you map each distinct triple to a unique bucket. |
|
