多少个点位于同一直线

	需要两重循环，第一重循环遍历起始点a，第二重循环遍历剩余点b。



	a和b如果不重合，就可以确定一条直线。



	对于每个点a，构建 斜率->点数 的map。



	(1)b与a重合，以a起始的所有直线点数+1 (用dup统一相加)



	(2)b与a不重合，a与b确定的直线点数+1

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int size = points.size();
        if(size == 0)
            return 0;
        else if(size == 1)
            return 1;
            
        int ret = 0;
        for(int i = 0;i<size;i++){
            
            int curmax = 1;
            map<double,int>mp;
            int vcnt = 0; //垂直点
            int dup = 0; //重复点
            for(int j = 0;j<size;j++){
                
                if(j!=i){
                    double x1 = points[i].x - points[j].x;
                    double y1 = points[i].y - points[j].y;
                    if(x1 == 0 && y1 == 0){   //重复
                        dup++;
                    }else if(x1 == 0){      //垂直
                        if(vcnt == 0)
                            vcnt = 2;
                        else
                            vcnt++;
                        curmax = max(vcnt,curmax);
                    }else{ 
                        double k = y1/x1;          //斜率
                        if(mp[k] == 0)
                            mp[k] = 2;
                        else
                            mp[k]++;
                        curmax = max(mp[k],curmax);
                    }                    
                }
            }
            ret = max(ret,curmax+dup);            
        }
        return ret;
        
    }
};

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
import java.util.*;

public class Solution {
    public int maxPoints(Point[] points) {
        int n = points.length;
        if(n < 2) return n;
        
        int ret = 0;
        for(int i = 0; i < n; i++) {
            // 分别统计与点i重合以及垂直的点的个数
            int dup = 1, vtl = 0;
            Map<Float, Integer> map = new HashMap<>();
            Point a = points[i];
            
            for(int j = 0; j < n; j++) {
                if(i == j) continue;
                Point b = points[j];
                if(a.x == b.x) {
                    if(a.y == b.y) dup++;
                    else vtl++;
                } else {
                    float k = (float)(a.y - b.y) / (a.x - b.x);
                    if(map.get(k) == null) map.put(k, 1);
                    else map.put(k, map.get(k) + 1);
                }
            }
            
            int max = vtl;
            for(float k: map.keySet()) {
                max = Math.max(max, map.get(k));
            }
            ret = Math.max(ret, max + dup);
        }
        return ret;
    }
}

//本方法在高票答案的基础上做了以下优化：
//1、map的键值修改为：对斜率保留6位小数的string，以避免浮点数直接比较
//2、内存循环从i+1开始，避免不必要的循环
//3、对于高票答案中讨论的vCn，dCn 初值设为1的“优化方案”进行否定，
//因为初值为1可能导致一些边界异常，需要在结尾处处理异常，反而增加了工作量
class Solution {
public:
	int maxPoints(vector<Point> &points) {
		if(points.size() == 0)
			return 0;
		else if(points.size() == 1)
			return 1;
		int res = 1;
		for(size_t i = 0; i < points.size(); ++i){
            map<string, int>info;
			int vCn = 0/*垂直点 */, dCn = 0/*重复点 */, curMax = 1/*当前最大连接点数 */;
			for(size_t j = i+1; j < points.size(); ++j){
				double x_dis = points[i].x - points[j].x;
				double y_dis = points[i].y - points[j].y;
				if(compare(points[i].x , points[j].x) && compare(points[i].y , points[j].y) ){
					++dCn;
				}
				else if( compare(x_dis, 0.0) ) {                    
					if(vCn == 0)
						vCn = 2;
					else
						++vCn;
					curMax = curMax > vCn ? curMax : vCn;
				}
				else{
					double k = y_dis/x_dis;
					string sk = transform(k);
					if(info[sk] == 0)
						info[sk] = 2;
					else
						++info[sk];
					curMax = curMax > info[sk] ? curMax : info[sk];
				}                                 
			}
			res = res > curMax + dCn ? res : curMax + dCn;
		}
		return res;
	}

	string transform(double d){
		ostringstream os; 
		os << ( (int)(d * 1000000 + 0.5) ) / 1000000.0;
		return os.str();;
	} 

	bool compare(double a, double b){
		if( fabs(a - b) < 1e-6) 
			return true; 
		else
			return false;
	} 
};

import java.util.*;
public class Solution {
   public int maxPoints(Point[] points) {
		if(points.length < 2) return points.length;
		int max = 0;
		for (int i = 0; i < points.length; i ++) {
			Map<Float, Integer> map = new HashMap<>();
			int chonghe = 0, chuizhi = 0;
			Point a = points[i];
			for (int j = 0; j < points.length; j ++) {
				if(i == j) continue;
				Point b = points[j];
				if(a.x == b.x) {
					if(a.y == b.y) chonghe ++;
					else chuizhi ++;
				} else {
					float k = (float)(a.y - b.y) / (a.x - b.x);
					map.put(k, map.get(k) == null ? 1 : map.get(k) + 1);
				}
			}
			int temp_max = chuizhi;
			for (Float k:map.keySet()) {
				temp_max = temp_max > map.get(k) ? temp_max : map.get(k);
			}
			max = max > temp_max + chonghe + 1 ? max : temp_max + chonghe + 1;
		}
		return max;
	}
}

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        sort(points.begin(), points.end(), [](Point a, Point b){return a.x < b.x;});
        long long ans = 0;
        for (int i = 0; i < points.size(); i++)
        {
            map<pair<int, int>, long long> k;
            long long multi = 0, vertical = 0, maxk = 0;
            for (int j = i + 1; j < points.size(); j++)
            {
                if (points[i].x == points[j].x && points[i].y == points[j].y)
                {
                    multi++;
                }
                else if (points[i].x == points[j].x)
                {
                    maxk = max(maxk, ++vertical);
                }
                else
                {
                    int x = points[j].x - points[i].x;
                    int y = points[j].y - points[i].y;
                    int g = __gcd(x, y);
                    x /= g, y /= g;
                    maxk = max(maxk, ++k[make_pair(x, y)]);
                }
            }
            ans = max(ans, maxk + multi + 1);
        }
        return ans;
    }
};

/**

//参考了排名最高的回答，但是不可以采用double形式来表达，因为会产生精度误差，我们可以
//使用分数的形式来表示斜率，使用分子分母同除以最大公倍数即可得到最简分数；
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int size = points.size();
        if(size<=2) return size;     
        int ret = 0;
        for(int i = 0;i<size;i++)
        {
            int curmax = 0;
            map<string,int>mp;
            int vcnt = 0; //垂直点
            int dup = 0; //重复点
            for(int j = 0;j<size;j++)
            {
                int x1 = points[i].x - points[j].x;
                int y1 = points[i].y - points[j].y;
                if(x1==0 && y1==0)
                    dup++;
                else if(y1==0)
                {
                    ++vcnt;
                    curmax = max(curmax,vcnt);
                }
                else 
                {
                    string key = gcb(y1,x1);
                    ++mp[key];
                    curmax = max(curmax,mp[key]);
                }
            }
            ret = max(ret,curmax+dup);           
        }
        return ret;
    }
    string gcb(int y1,int x1)   //使用分子分母表示最简分数
    {
        if(x1==0)
            return "shuipin";
        int a = y1;
        int b = x1;
        int temp;
        while(a%b)
        {
           temp = a%b;
           a = b;
           b = temp;
        }
        return to_string(y1/b) + "/" + to_string(x1/b); 
    }
};

public int maxPoints(Point[] points) {
        Double k;
        int x, y, max = 0;
        for(int i = 0; i < points.length; i++) {
        	HashMap<Double, Integer> map = new HashMap<Double, Integer>();
        	int curMax = 1, repNum = 0;
            x = points[i].x; y = points[i].y;
            for(int j = i + 1; j < points.length; j++) {
            	int num = 1;
                if(x == points[j].x && y == points[j].y)
                	repNum += 1;
                else {
                	if(x != points[j].x)
                		if(y == points[j].y)	k=0.0;
                		else k = 1.0*(y - points[j].y) / (x - points[j].x);
                	else
                        k = Double.MAX_VALUE;
                	
                    if(map.get(k) != null)
                        num = map.get(k) + 1;
                    else
                    	num = 2;
                    map.put(k, num);
                } 
                
                if(curMax < num)	curMax = num;
                
            }
            
            curMax += repNum;
            if(max < curMax) max = curMax;
        }
        return max;
    }

class Solution {
public:
bool CalculateLine(const Point& p1,
                   const Point& p2,
                   vector<double>* line_para_ptr) {
    vector<double>& line_para = *line_para_ptr;
    if (p1.x - p2.x == 0)
        return false;
    double k = (double)(p1.y - p2.y)/(double)(p1.x - p2.x);
    double b = p2.y - p2.x * k;
    line_para.push_back(k);
    line_para.push_back(b);
    return true;
}

bool JudgePointAtLine(const Point& p,
                      const vector<double>& line_para) {
    return abs(p.y - line_para[0] * p.x - line_para[1]) < 1e-8;
}

int maxPoints(vector<Point>& points) {
    int nsize = points.size();
    if (nsize == 0)
        return 0;
    else if (nsize == 1)
        return 1;
    else if (nsize == 2)
        return 2;
    int maxpoints = 0;
    vector<set<int>> common_line_points_index;
    common_line_points_index.resize(nsize);
    for (int i = 0; i < nsize; i++) {
        for (int j = i + 1; j < nsize; j++) {
            if (common_line_points_index[j].count(i))
                continue;
            bool have_gradient;
            vector<double> line_par;
            int numpoints = 2;
            have_gradient = CalculateLine(points[i], points[j], &line_par);
            common_line_points_index[i].insert(j);
            common_line_points_index[j].insert(i);
            for (int k = 0; k < nsize; k++) {
                if (k == i || k == j)
                    continue;
                if (!have_gradient) {
                    if (points[k].x == points[j].x)
                        numpoints++;
                } else {
                    if (JudgePointAtLine(points[k],line_par))
                        numpoints++;
                }
            }
            maxpoints = max(maxpoints, numpoints);
        }
    }
    return maxpoints;
}
};

class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int n = points.size();
        if(n <= 1)
            return n;
        int count = 0;
        for(int i=0;i<n;i++)
        {
            map<pair<int,int>,int> M;             int d = 1;             for(int j=i+1;j<n;j++)             {                 if(points[i].x==points[j].x && points[i].y==points[j].y)                 {                     d++;                     continue;                 }                 int dx = points[j].x - points[i].x;                 int dy = points[j].y - points[i].y;                 int g = gcd(dx, dy);                 M[{dx/g, dy/g}]++;             }             count = max(count, d);             for(auto it=M.begin();it!=M.end();it++)                 count = max(count, it->second + d);         }         return count;
    }
    int gcd(int a,int b)
    {
        return (b==0)?a:gcd(b,a%b);     }
};

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
import java.util.HashMap;
import java.util.Map;


public class Solution {
     public int maxPoints(Point[] points) {
		if (points == null)
			return 0;
		if (points.length <= 2)
			return points.length;
		Map<Integer, Map<Integer, Integer>> map = new HashMap<Integer, Map<Integer, Integer>>();
		int res=0;
		int max=0;
		for (int i = 0; i < points.length - 1; i++) {
            map.clear();
			int overLap = 0;
            max=0;
			for (int j = i + 1; j < points.length; j++) {
				int x = points[j].x - points[i].x;
				int y = points[j].y - points[i].y;
				if (x == 0 && y == 0){
					overLap++;
					continue;
				}
				// 计算最大公约数：欧几里得算法
				// 因为用分数代替斜率，所以必须保证分子分母最简
				int gcd = generateGCD(x, y);
				if (gcd != 0) {
					x = x / gcd;
					y = y / gcd;
				}
				if (map.containsKey(x)) {
					if (map.get(x).containsKey(y))
						map.get(x).put(y, map.get(x).get(y) + 1);
					else
						map.get(x).put(y, 1);
				} else {
					Map<Integer,Integer> temp=new HashMap<Integer,Integer>();
					temp.put(y, 1);
					map.put(x, temp);
				}
				max=Math.max(max,map.get(x).get(y));
			}
			res=Math.max(res, max+overLap+1);
		}

		return res;
	}

	private int generateGCD(int x, int y) {
		if(y==0)
			return x;
		return generateGCD(y,x%y);
	}
}

class Solution {
public:
     int maxPoints(vector<Point>& points) 
    {
       int len = points.size();
       if(len< 2)
            return len;
       int res = 0;
       for(int i=0;i<len;i++)
       {
           map<pair<int,int>,int> slopeMap;
           int duplicates = 1;         // 自身重叠初始化为1
           for(int j=i+1;j<len;j++)
           {
               // 重合
               if(points[i].x == points[j].x  && points[i].y ==  points[j].y)
               {
                   duplicates++;
                   continue;
               }
               // 斜率不适用float作为键，精度损失，使用除以最小公约数后的pair作为键
               int dix = points[j].x - points[i].x;
               int diy = points[j].y - points[i].y;
               int maxD = gcd(dix,diy);
               slopeMap[{dix/maxD,diy/maxD}] ++;
           }
           res = max(res,duplicates);
           for(auto it=slopeMap.begin();it!=slopeMap.end();it++)
                res = max(res,it->second + duplicates);
       }
       return res;
    }
    int gcd(int a, int b) 
    {
        return (b == 0) ? a : gcd(b, a % b);
    }
};

/*
 *分为n、n-1、n-2……3等组（每组分别包含n个点、n-1个点……），找到每组中包含第一个点的点数最多的直线（每个点与第一个点有一个斜率，通过斜率是否相等判断是否在同一条直线），则每组结果的最大值即为所求；
 *原理：所求直线所包含的点，一定有一个最靠前的i点，使得直线上所有点为i~1的子集，所求值即为i组的结果
 *注意事项：1、存在与第一个点相同的点；2、使用浮点数不一定能准确的表示斜率，在此使用由String表示的分数来表示斜率
*/
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
class Solution {
    public int maxPoints(Point[] points) {
        int result=0;
        if(points.length<3) return points.length;
        for(int i=0;i<points.length-1;i++){
            HashMap map=new HashMap();
            int maxNum=0,sameAsI=0;
            for(int j=i+1;j<points.length;j++){
                String key=xieLv(points[i],points[j]);
                if(points[i].x==points[j].x&&points[i].y==points[j].y) {
                    sameAsI++;
                    continue;
                }else {
                    map.put(key,map.containsKey(key) ? map.get(key)+1:1);
                }
                maxNum= Math.max(maxNum,map.get(key));
            }
            result=Math.max(result,maxNum+sameAsI);
        }
        return result+1;
    }

    private String xieLv(Point a,Point b){
        int x=a.x-b.x,y=a.y-b.y;
        if(x==0) return fuHao(x,y)+"ANY"+"/"+0;
        else if(y==0) return fuHao(x,y)+0+"/"+"ANY";
        int gcb=gcb(Math.abs(y),Math.abs(x));
        return fuHao(x,y)+Math.abs(y)/gcb+"/"+Math.abs(x)/gcb;
    }
    private String fuHao(int x,int y){
        if(x>=0&&y>=0||x<=0&&y<=0){
            return "+";
        }else return "-";
    }
    private int gcb(int a,int b){
        if(b==0) return a;
        else return gcb(b,a%b);
    }
}

if(points.size() < 2)
            return points.size();

        int result = 0;
        for(int i=0;i<points.size();++i)
        {
            //用来记录斜率和个数的Map
            map, int> lines;
            int localmax = 0, overlap = 0, vertical = 0;
            for(int j=i+1;j<points.size();++j)
            {
                if(points[i].x == points[j].x&&points[i].y == points[j].y)
                {
                    ++overlap;
            continue;
                }else if(points[i].x == points[j].x)
                {
                    ++vertical;
                    localmax = max(localmax, vertical);
                }else{
                    int x = points[j].x - points[i].x;
                    int y = points[j].y - points[i].y;
                    int gcd = GCD(x, y);
                    x /= gcd;
                    y /= gcd;
                    ++lines[make_pair(x,y)];
                    localmax = max(localmax, lines[make_pair(x,y)]);
                }     
            }
            result = max(result, localmax+overlap+1);
        }

        return result;
    }
private:
    //求得最大公约数
    int GCD(int a, int b)
    {
        if(b==0)
            return a;
        else
            return GCD(b, a%b);
    }

/**
 * struct Point {
 *	int x;
 *	int y;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param points Point类vector 
     * @return int整型
     */
    int maxPoints(vector<Point>& points) {
        // write code here
        size_t ps = points.size();
        if(ps <=2) return ps;

        int ans = 0;
        for(size_t i=0; i<ps; ++i){
            int groupmax = 0, dup = 1, ver = 0;
             map<double, int> kgroup;
            for(size_t j=i+1; j<ps; ++j){
                double dx = points[i].x-points[j].x;
                double dy = points[i].y-points[j].y;
                
                if(dx==0 && dy==0)
                    ++dup;
                else if(dx==0){
                    ++ver;
                }else{
                    ++kgroup[dy/dx];
                    groupmax = max(groupmax, kgroup[dy/dx]);
                }    
            }
            ans = max(ans, max(groupmax, ver) + dup);
        }
        return ans;
    }
};

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 * }
 */

public class Solution {
    /**
     * 
     * @param points Point类一维数组 
     * @return int整型
     两层for循环遍历每两个点，总共考虑三种情况：
     （1）两点重合
     （2）两点垂直（因为两点垂直无法计算斜率）
     （3）两点平行或者倾斜（计算斜率）
     */
        public int maxPoints (Point[] points) {
        if(points.length <= 2){
            return points.length;
        }
        int count = 0;
        for(int i = 0; i < points.length; i++){
            HashMap<Float, Integer> map = new HashMap<>();//存放斜率以及斜率出现的次数
            Point a = points[i];
            int chonghe = 0;
            int chuizhi = 0;
            for(int j = 0; j < points.length; j++){
                Point b = points[j];
                if(i == j) continue;
                if(a.x == b.x){
                    if(a.y == b.y){
                        chonghe++;//xy坐标均相等即重合的情况
                    }else{
                        chuizhi++;//x坐标相等y不相等，即垂直的情况
                    }
                }else{ //第三种情况
                    float rate = (float)(b.y - a.y)/(b.x - a.x);
                    map.put(rate, map.get(rate) == null ? 1: map.get(rate) + 1);
                }
                int maxTemp = chuizhi;
                for(Integer value : map.values()){ //计算斜率相同的点最多有多少个
                    maxTemp = maxTemp > value ? maxTemp : value;//与垂直的情况进行对比
                }
                count = count > maxTemp+chonghe+1 ? count : maxTemp+chonghe+1;
            }
        }
            return count;
}
    
}