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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 还有一个问题就是,如果用unordered_map,写运算符是简单了,只需要写==运算符, : 但是hash function要自己写?这个怎么理解呢?为什么map只要重载运算符就行。
|