class DenseLine {
public:
    vector<double> getLine(vector<Point> p, int n) {
        map<pair<double, double>, int > lines;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                ++lines[calLine(p[i],p[j])];
            }
        }
        auto it = lines.begin();
        auto maxLine = it;
        int max = 0;
        while(it != lines.end()){
            if(it->second > max) maxLine = it;
            it++;
        }
        vector<double> res;
        res.push_back(maxLine->first.first);
        res.push_back(maxLine->first.second);
        return res;
    }

   //计算斜率 
    pair<double, double> calLine(Point p1,Point p2){
        double k = (double)(p1.y - p2.y)/(double)(p1.x - p2.x);
        double s = (double)p1.y - (double)k*p1.x;
        return make_pair(k,s);
    }
};

public class DenseLine {
   public double[] getLine(Point[] p, int n) {
       HashMap<Line,Integer> lineNum=new HashMap<Line,Integer>();
       int max=0;
       double slope=Double.POSITIVE_INFINITY,intercept=0;
       //把所有线取出来求出斜率和截距,并用哈希图存储下线条和个数的键值对
       for(int i=0;i<n;i++){
           for(int j=i+1;j<n;j++){
               double k=(double)(p[j].y-p[i].y)/(p[j].x-p[i].x);
               double b=(double)(p[i].y-k*p[i].x);
               Line line=new Line(k,b);
               if(lineNum.containsKey(line)){
                   int num=lineNum.get(line)+1;
                   lineNum.put(line,num);
                   //不断调整最大值
                   if(num>max){
                       max=num;
                       slope=k;
                       intercept=b;
                   }
               }
               else
                   lineNum.put(line,1);
           }
       }
       return new double[]{slope,intercept};
   }
}

//面向对象的编程思想
class Line{
    double k;  //斜率
    double b;  //截距
    double epsilon=0.0001; //误差
    public Line(double k,double b){
        this.k=k;
        this.b=b;
    }
    //比较两个double是否相等
    public boolean isEqualValue(double a,double b){
        return (Math.abs(a-b)<epsilon);
    }
    //重写equals方法当此方法被重写时，通常有必要重写 hashCode 方法，
    //以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。
    public boolean equals(Object obj) {
        if (obj instanceof Line) {
            if(isEqualValue(k,((Line)obj).k)&&isEqualValue(b,((Line)obj).b))
               return true;
            return false;
        }
        return super.equals(obj);
    }
    //HashMap对应的应该是HashSet，数据结构是哈希表，先比hashCode()，再比equals
    public int hashCode() {
    	String str=String.valueOf(k)+String.valueOf(b);
        return str.hashCode();           
    }
}

    static class Line {
		double k, b;

		public Line(double k, double b) {
			this.k = round(k);
			this.b = round(b);
		}

		double round(double x) {
			double e = 0.00001;
			return ((int) (x / e)) * e;
		}

		public int hashCode() {
			return (int) (k + b);
		}

		public boolean equals(Object obj) {
			Line l = (Line) obj;
			return l.b == b && l.k == k;
		}
	}

	public double[] getLine(Point[] p, int n) {
		HashMap<Line, Integer> map = new HashMap<>();
		double mk = 0, mb = 0;
		for (int i = 0, max = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				double k = (p[i].y - p[j].y) / (p[i].x - p[j].x);
				double b = p[i].y - k * p[i].x;
				Line l = new Line(k, b);
				Integer cnt = map.get(l);
				if (cnt == null) {
					map.put(l, 1);
                    cnt = 1;
				} else {
					map.put(l, ++cnt);
				}
				if (cnt > max) {
					max = cnt;
					mk = k;
					mb = b;
				}
			}
		}
		return new double[] { mk, mb };
	}

import java.util.*;
/*
思路：遍历所有的直线，求出他们的斜率，找出其中相同斜率数最多的直线，这条直线就是所需要的斜线
利用到了hashmap，斜率和斜率对应的数目构成了键值对
但是我感觉我这个复杂度很高
*/
/*
public 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;
    }
}*/
public class DenseLine {
    
    public double[] getLine(Point[] p, int n) {
		HashMap<Double,Integer> h =new HashMap<Double,Integer>();
    	int max=0;
        double temp=0.0;
        Point pTemp =null;
        for(int i=0;i<p.length;i++){
			for(int j=i;j<p.length;j++){
                if(p[j].x ==p[i].x){
                    continue;
                } 
                double k=(p[j].y-p[i].y)/(p[j].x-p[i].x);
                if(h.get(k) ==null){
                    h.put(k,1);
                }else{
                    int count =h.get(k);
                    h.put(k,count+1);
                }
                if(h.get(k)>max){
                    max=h.get(k);
                    pTemp =p[i];
                    temp=k;
                }
            }
    	}
        double s=pTemp.y-temp*pTemp.x;
        double [] d=new double[2];
        d[0]=temp;
        d[1]=s;
        return d;
    }
}
运行时间：301ms
占用内存：19868k

class DenseLine {
public:
    vector<double> getLine(vector<Point> p, int n) {
        // write code here
        map<double ,map<double,int >> m;
        double k,b;
        for (int i = 0; i < p.size(); ++i) {
            for (int j = i + 1; j < p.size(); ++j) {
                k = (p[i].y - p[j].y) * 1.0 / (p[i].x - p[j].x);
                b = p[i].y - k * p[i].x;
                m[k][b] ++;
            }
        }
        int max = INT_MIN;
        vector<double > res;
        auto it = m.begin();
        while (it != m.end()){
            auto t = it ->second.begin();
            while (t != it -> second.end()){
                if(t -> second > max){
                    max = t -> second;
                    k = it -> first;
                    b = t -> first;
                }
                t ++;
            }
            it ++;
        }
        res.push_back(k);
        res.push_back(b);
        return res;
    }
};

	

public static double[] getLine(Point[] p, int n)
        {
            //哎，这个在线编译器不支持c#泛型Dictionary，也不支持Hashtable
            Dictionary <Line,int> dict=new Dictionary<Line,int>();
            Line line= new Line();
            double slope=double.PositiveInfinity,intercept=0;
            int max=0;
            for(int i=0;i<n-1;i++)
            {                
                for(int j=i+1;j<n;j++)
                {
                    line.k=(double)(p[i].Y-p[j].Y)/(double)(p[i].X-p[j].X);
                    line.b=(double)p[i].Y-(double)line.k*p[i].X;
                }
                if(dict.ContainsKey(line))
                {
                    dict[line] += 1;                     
                    if (dict[line]>max)
                    {
                        max=dict[line];
                        slope=line.k;
                        intercept=line.b;
                    }                    
                    /*或者如下
                    int count =(dict[line])+1;                    
                    dict.Remove(line);                   
                    dict.Add(line,count);
                    if(count>max)
                    {
                        max=count;
                        slope=line.k;
                        intercept=line.b;
                    }                    
                    */  
                }
                else
                {
                    dict.Add(line,1);                   
                }
            }
            return new double[] { slope, intercept };
        }         

//写完了看看别人的代码，都比我简洁，我就不贴代码了。这个题目还可以使用哈希表完成；
思路如下：
/*
共线最多的点的个数
思路：可以看所有两点能够构造的直线的斜率，根据斜率来判断共线的点的个数 
这样斜率和该斜率上点的个数就构成了一个键值对，可以使用hash表来存储 
*/

int maxPoints(vector<pair<int,int> >& points )
{
	if(points.size() == 0)
		return 0;
	int max =1;
	double ratio=0.0;//斜率
	//开始遍历点，构造键值对
	for(int i=0;i<points.size()-1;i++)
	{
		hash_map<double,int> map;
		int numofSame=0;
		int localMax=1;
		//从当前点和其之后的点构成的斜率 
		for(int j=i+1;j<points.size();j++)
		{
			//统计相同的点，横坐标相同、纵坐标相同，记为同一个点
			if(points[j].first == points[i].first && points[j].second == points[i].second)
			{
				numofSame++;
				continue; 
			}
			//斜率无穷大的，记为numeric_limits<double>::max()最大值
			else if(points[j].first == points[i].first)
			{
				ratio = numeric_limits<double>::max();
			}
			//纵坐标相同，斜率为0的情况
			else if(points[j].second == points[i].second)
			{
				ratio =0.0;
			}
			else//正常情况
			{
				ratio = (double)(points[j].second-points[i].second)/(double)(points[j].first-points[i].first);
				
			}
			int num;
			if(map.find(ratio) != map.end())//查找map，找到该斜率，找到说明多1个点共直线
				map[ratio]++;
			else//没有该斜率存在，就是2个点
				map[ratio]=2;
		} 		 
		//开始查找某一斜率下最多的点的个数
		hash_map<double,int>::iterator it = map.begin();
		fo(;it!=map.end();it++)
			localMax = max(localMax,it->second);//找到最大的点数
		localMax += numofSame;//加上相同的点值
		max = max(max,localMax); //更新max值
	}
	return max;
}

public class DenseLine {
    public double[] getLine(Point[] p, int n) {
        // write code here
        double[] re=new double[2];
		
		int num1=0;
		int num2=0;
		
		double te1,te2;
		
		for(int i=0;i<n-1;++i){
			for(int j=i;j<n;++j){
				num2=0;
				if(p[j].x==p[i].x){
					te1=0.0;
					te2=p[j].y;
				}else{
					te1=(p[j].y-p[i].y)/(p[j].x-p[i].x);
					te2=p[j].y-te1*p[j].x;
				}
				
				
				for(int k=0;k<n;++k){
					if(Math.abs(p[k].y-te1*p[k].x-te2)<0.0000001){
						++num2;
					}
				}
				
				if(num2>num1){
					re[0]=te1;
					re[1]=te2;
					num1=num2;
				}
			}
		}
		
		
		return re;
    }
}  求每两个点的直线，并判断其他点是否在直线上。

public static double[] getLine(Point[] p, int n) {                            
	// 记录直线的k和b, 以及额外点的个数                                                     
	double k = 0.0;                                                           
	double b = 0.0;                                                           
	int otherCount = 0;                                                       
                                                                              
	for (int i = 0; p != null && i < n; i++) {                                
		for (int j = i + 1; j < n; j++) {                                     
			// 记录当前点的k和b                                                      
			double temK = (double) (p[j].y - p[i].y) / (p[j].x - p[i].x);     
			double temB = p[j].y - temK * p[j].x;                             
			int temCount = 0;                                                 
			for (int l = j + 1; l < n; l++) {                                 
				double temK1 = (double) (p[l].y - p[i].y) / (p[l].x - p[i].x);
				double temB1 = p[l].y - temK1 * p[l].x;                       
				if(temK1 == temK && temB1 == temB){                           
					temCount ++;                                              
				}                                                             
			}                                                                 
			// 如果有更多的点就交换                                                     
			if(temCount > otherCount){                                        
				k = temK;                                                     
				b = temB;                                                     
				otherCount = temCount;                                        
			}                                                                 
		}                                                                     
	}                                                                         
	                                                                          
	if(otherCount == 0){                                                      
		return  new double[]{};                                               
	}                                                                         
	                                                                          
	return new double[]{k,b};                                                 
}                                                                             

public double[] getLine(Point[] p, int n) {
        // write code here
        List<Point[]> list = new ArrayList<Point[]>();
        p(p, new Point[p.length], new int[p.length], 0, list, 0);

        int max = 0;

        double[]result = new double[2];

        Map<String,Integer>map = new HashMap<String, Integer>();

        for (Point[] po : list) {
//            System.out.print(po[0].x + "," + po[0].y + "|");
//            System.out.print(po[1].x + "," + po[1].y);
//            System.out.println();

            double k = (po[0].y - po[1].y) / (po[0].x - po[1].x);
            double b = po[0].y - k * po[0].x;

            String d = k+","+b;
            if (map.get(d) == null) {
//                System.out.println(d);
                map.put(d,1);
                if (1> max) {
                    max = 1;
                    result[0] = k;
                    result[1] = b;
                }
            } else {
                map.put(d, map.get(d) + 1);
                if (map.get(d)> max) {
                    max = map.get(d);
                    result[0] = k;
                    result[1] = b;
                }
            }
        }
//        System.out.println(map);
        return result;
    }

    void p(Point[] a, Point[] aa, int[] book, int step, List<Point[]> list, int j) {
        if (2 == step) {
            list.add(new Point[]{aa[0], aa[1]});
        }

        for (int i = 0; i < a.length; i++) {
            if (book[i] == 0 && i >= j) {
                book[i] = 1;
                aa[step] = a[i];
                p(a, aa, book, step + 1, list, j);
                j++;
                book[i] = 0;
            }
        }
    }

class DenseLine {
public:
    vector<double> getLine(vector<Point> p, int n) {
        int max_points=0;
        double max_points_k;
        double max_points_b;
        for(int i=0;i<n-1;++i)
            for(int j=i+1;j<n;++j)
            {
                int count=0;
                double k=(p[j].y-p[i].y)/(p[j].x-p[i].x);
                double b=p[j].y-k*p[j].x;
                for(int m=j+1;m<n;++m)
                {
                    if(p[m].x*k+b==p[m].y)
                    {
                        count++;
                    }
                }
                if(count>max_points)
                {
                    max_points=count;
                    max_points_k=k;
                    max_points_b=b;
                }
            }
        return {max_points_k,max_points_b};
    }
};

class DenseLine:
    def getLine(self, p, n):
        # write code here
        if len(p)==2:
            k,b=self.getkb(p[0],p[1])
            return [k,b]
        i=0
        kbdict={}
        while i<=len(p)-1:
            j=i+1
            while j<=len(p)-1:
                k,b=self.getkb(p[i],p[j])
                kb=(k,b)
                if kb in kbdict:
                    kbdict[kb]+=1
                else:
                    kbdict[kb]=1
                j+=1
            i+=1
        maxpoint=0
        for kb in kbdict:
            if maxpoint<kbdict[kb]:
                maxpoint=kbdict[kb]
                k,b=kb
                ans=[k,b]
        return ans
                
    def getkb(self,p1,p2):
        k=(p2.y-p1.y)/(p2.x-p1.x)
        b=p2.y-k*(p2.x)
        return k,b

/*
struct Point {
    int x;
    int y;
    Point() :
            x(0), y(0) {
    }
    Point(int xx, int yy) {
        x = xx;
        y = yy;
    }
};*/
class DenseLine {
public:
    vector<double> getLine(vector<Point> p, int n) {
        // write code here
        map<pair<double,double>,int> map;
        vector<double> ans(2);
        for (int i=0;i<n;i++)
        {
            for (int j=i+1;j<n;j++)
            {
                double k=(p[i].y-p[j].y)/(p[i].x-p[j].x);
                double b = p[i].y-k*p[i].x;
                 if (map.find({k,b})==map.end())
                     map[{k,b}]=1;
                 else
                     map[{k,b}]++;
            }
        }
        int max =0;
        for(auto it=map.begin();it!=map.end();it++)  //遍历表
        {
            if (it->second >max)    //如果某一点对的出现的次数大于最大值
            {
                ans[0]= it->first.first;  //将点对的值（斜率，截距）赋给输出结果
                ans[1]= it->first.second;
                max = it->second;
            }
        }
        return ans;
    }
};

由 y=k*x + b 使用循环遍历，统计每个k和b出现的次数，返回次数最多的k和吧

# -*- coding:utf-8 -*-

# class Point:
#     def __init__(self, a=0, b=0):
#         self.x = a
#         self.y = b
class DenseLine:
    def getLine(self, p, n):
        # write code here
        m = [0,0]
        res = {}
        count = 0
        for i in range(n):
            for j in range(i+1,n):
                k = (p[i].y -p[j].y )/(p[i].x - p[j].x)
                res[k] = res.get(k,0) + 1
                if res[k] > count:
                    m[0] = k
                    m[1] = p[i].y - p[i].x*k
                    count = res[k]
        return m

// 遍历所有组合，暴力算法（暂时没想到非暴力的算法）
class DenseLine {
public:
    vector<double> getLine(vector<Point> p, int n) {
        // write code here
        map<pair<double,double>, int> mapCount;
        for (int i = 0; i < p.size(); i++) {
            for (int j = i + 1; j < p.size(); j++) {
                mapCount[calPair(p[i], p[j])]++;
            }
        }
        pair<double, double> pairResult;
        int max = -1;
        for (auto it = mapCount.begin(); it != mapCount.end(); it++) {
            if (it->second >max) {
                max = it->second;
                pairResult = it->first;
            }
        }
        vector<double> result;
        result.push_back(pairResult.first);
        result.push_back(pairResult.second);
        return result;
    }
    pair<double, double> calPair(Point A, Point B) {
        double slope;
        double intercept;
        slope = (B.y - A.y) / (B.x - A.x);
        intercept = B.y - slope * B.x;
        return make_pair(slope, intercept);
    }
};