首页 > 试题广场 >

穿点最多的直线

[编程题]穿点最多的直线
  • 热度指数：5615 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

已知一个点集vector<point>p和点集的大小n,点都在一个二维平面上且横坐标各不相同,找到一条穿过点数最多的直线，返回值为vector<double>，代表所求直线的斜率和截距。</double></point>

算法知识视频讲解
添加回答
Java
EvanTaurus头像 EvanTaurus
import java.util.*;
import java.util.Map.Entry;
class Point {
    int x;
    int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public Point() {
        this.x = 0;
        this.y = 0;
    }
}

class Line {
double k;
double b;
public Line(double k, double b) {
this.k = k;
this.b = b;
}
public Line() {
this.k = 0;
this.b = 0;
}
public boolean equals(Object o) {
Line l = (Line) o;
if (this.b == l.b && this.k == l.k)
return true;
return false;
}
}


public class DenseLine {
public Line getLine(Point p1, Point p2) {
double k = (p2.y - p1.y) / (p2.x - p1.x);
double b = p1.y - k * p1.x;
Line l = new Line(k,b);
return l;
}
    public double[] getLine(Point[] p, int n) {
        HashMap<Line,Integer> hm = new HashMap<Line,Integer>();
        for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
        Line l = getLine(p[i],p[j]);
        if (hm.containsKey(l)) {
        int val = hm.get(l);
        val += 1;
        hm.put(l, val);
        } else {
        hm.put(l,1);
        }
        }
        }
        Line max = null;
        int fre = 0;
        Iterator it = hm.entrySet().iterator();
        while (it.hasNext()) {
        Map.Entry<Line, Integer> m = (Entry<Line, Integer>) it.next();
        Line temp = m.getKey();
        int val = m.getValue();
        if (val > fre) {
        max = temp;
        fre = val;
        }
        }
        double[] res = {max.k,max.b};
        return res;
        
    }
}
发表于 2017-04-06 15:05:01 回复(0)
提交观点

问题信息

编程基础 模拟 哈希 基础数学
难度：
1条回答 48773浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号