Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
需要兩重循環(huán)，第一重循環(huán)遍歷起始點(diǎn)a，第二重循環(huán)遍歷剩余點(diǎn)b。 a和b如果不重合，就可以確定一條直線。 對(duì)于每個(gè)點(diǎn)a，構(gòu)建 斜率->點(diǎn)數(shù) 的map。 (1)b與a重合，以a起始的所有直線點(diǎn)數(shù)+1 (用dup統(tǒng)一相加) (2)b與a不重合，a與b確定的直線點(diǎn)數(shù)+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; //垂直點(diǎn) int dup = 0; //重復(fù)點(diǎn) 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){ //重復(fù) 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; }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
