s********u
发帖数: 1109 | 1 做了一下7.6，就是找经过点最多的直线。
答案给的比较复杂，是用一个 >的hashmap，在斜率匹配的情况
下，再去vector找匹配的line，而且感觉有bug，在匹配斜率的时候没有考虑斜率无穷
大的情况。
我想了一下C++的做法，比较直观的做法是建立 的hashtable,然后重载一下
预算符，当斜率差和截距差都小于eps = 0.0001的时候视作两条线是同一条线。
但是因为重载这一块不太熟，不知道写的对不对，请大牛们指点一下：
//Given a two-dimensional graph with points on it,find a line which passes
the most number of points.
class Line{
private:
double slope;
double intercept;
bool infinity_slope;
static double eps;
public:
Line(Point1 p1,Point2 p2){
if( abs(p1.x - p2.x) < 0 ){
infinity_slope = true;
intercept = p1.x;
}else{
slope = (p1.y - p2.y)/(p1.x - p2.x);
intercept = p1.y - slope * p1.x;
}
}
bool operator<(const Line& l)const{
if( infinity_slope&& l.infinity_slope )
return (intercept - l.intercept) >= eps);
if( infinity_slope)
return true;
if( l.infinity_slope)
return false;
if( (slope - l.slope) >= eps )
return true;
if( (slope - l.slope) <= (-1) * eps )
return false;
if( (intercept - l.intercept) >= eps )
return true;
if( (intercept - l.intercept) <= (-1)*eps )
return false; //false的情况需要写么？
return false;
}
};
double Line::eps = 0.0001;
Line findBestLine( Point points[],int size){
map lmap;
int count = 0;
Line bestline;
for( int i = 0; i < size; i++){
for( int j = i + 1; i < size; j++){
Line line( points[i], points[j] );
lmap[line]++;
if( lmap[line] > count ){
count = lmap[line];
bestline = line;
}
}
}
return bestline;
}
我查了一下，map的count或者find，应该都是只依赖运算符<的，也就是说只要差值小
于eps，map就会视作相同的key，是这么个道理吧？ |
s********u
发帖数: 1109 | 2 还有一个问题就是，如果用unordered_map，写运算符是简单了，只需要写==运算符，
但是hash function要自己写？这个怎么理解呢？为什么map只要重载运算符就行。 |
T*******e
发帖数: 4928 | |
s********u
发帖数: 1109 | 4 Thank you so much!
【在 T*******e 的大作中提到】
: see solution in the end of the following page.
: http://www.itint5.com/discuss/237/%E5%A6%82%E6%9E%9C%E7%94%A8%E
|
a******e
发帖数: 710 | 5 ==是判断相等用的。和hash func是独立的。即使两个元素hash value一样， 他们也不
一定相等。这时候就要用到==
map是红黑树。只要定义<=就行了
还有一个问题就是，如果用unordered_map，写运算符是简单了，只需要写==运算符，
但是hash function要自己写？这个怎么理解呢？为什么map只要重载运算符就行......
..
【在 s********u 的大作中提到】
: 还有一个问题就是，如果用unordered_map，写运算符是简单了，只需要写==运算符，
: 但是hash function要自己写？这个怎么理解呢？为什么map只要重载运算符就行。
|
