Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
A better solution:
1 /** 2 * Definition for a point. 3 * class Point { 4 * int x; 5 * int y; 6 * Point() { x = 0; y = 0; } 7 * Point(int a, int b) { x = a; y = b; } 8 * } 9 */ 10 class Line{ 11 //a/b = (y1-y2)/(x1-x2), c/d=(x1y2-x2y1)/(x1-x2) 12 int a, b, c, d; 13 String uid; 14 Set pList; 15 public Line(Point p1, Point p2){ 16 pList = new HashSet (); 17 a = p1.y-p2.y; 18 b = p1.x-p2.x; 19 c = p1.x*p2.y-p2.x*p1.y; 20 d = p1.x - p2.x; 21 22 if (a==0){ 23 a = 0; 24 b = 1; 25 c = p1.y; 26 d = 1; 27 } else if (b==0){ 28 a = 1; 29 b = 0; 30 c = p1.x; 31 d = 1; 32 } else { 33 int gcd = getGCD(a,b); 34 a = a/gcd; 35 b = b/gcd; 36 if (b<0 && a>0){ 37 a = -a; 38 b = -b; 39 } 40 gcd = getGCD(c,d); 41 c = c/gcd; 42 d = d/gcd; 43 if (d<0 && c>0){ 44 c = -c; 45 d = -d; 46 } 47 } 48 //generate uid 49 setUID(); 50 } 51 52 public void setUID(){ 53 uid = a + "/" + b + "/" + c + "/" + d; 54 } 55 56 public String getUID(){ 57 return uid; 58 } 59 60 private int getGCD(int x, int y){ 61 while (y!=0){ 62 int val = x % y; 63 x = y; 64 y = val; 65 } 66 return x; 67 } 68 } 69 70 public class Solution { 71 public int maxPoints(Point[] points) { 72 if (points.length<3) return points.length; 73 74 int res = 0; 75 Map pMap = new HashMap (); 76 for (int i=0;i lineMap = new HashMap (); 84 Iterator iter1 = pMap.entrySet().iterator(); 85 while (iter1.hasNext()){ 86 Map.Entry en1 = (Map.Entry) iter1.next(); 87 int val = (int) en1.getValue(); 88 if (res pMap2 = new HashMap (); 91 pMap2.putAll(pMap); 92 pMap2.remove(p1); 93 while (!pMap2.isEmpty()){ 94 Iterator iter2 = pMap2.entrySet().iterator(); 95 Map.Entry en2 = (Map.Entry) iter2.next(); 96 Point p2 = (Point) en2.getKey(); 97 Line l1 = new Line(p1,p2); 98 String uid = l1.getUID(); 99 if (lineMap.containsKey(uid)){100 Line l2 = lineMap.get(uid);101 l2.pList.add(p1);102 l2.pList.add(p2);103 for (Point p: l2.pList) 104 pMap2.remove(p);105 } else {106 l1.pList.add(p1);107 l1.pList.add(p2);108 pMap2.remove(p2);109 lineMap.put(l1.getUID(),l1);110 }111 }112 }113 114 iter1 = lineMap.entrySet().iterator();115 while (iter1.hasNext()){116 Map.Entry en = (Map.Entry) iter1.next();117 Line l1 = (Line) en.getValue();118 int pNum = 0;119 for (Point p: l1.pList)120 pNum += pMap.get(p);121 if (res
Solution:
1 /** 2 * Definition for a point. 3 * class Point { 4 * int x; 5 * int y; 6 * Point() { x = 0; y = 0; } 7 * Point(int a, int b) { x = a; y = b; } 8 * } 9 */ 10 11 class Line { 12 int slopeX; 13 int slopeY; 14 int b; 15 boolean negSlope; 16 boolean samePointLine; 17 Set pointSet; 18 String uid; 19 public Line(int sx, int sy, int bb,boolean spl){ 20 if (sx<0) slopeX = -sx; 21 else slopeX = sx; 22 23 if (sy<0) slopeY = -sy; 24 else slopeY = sy; 25 26 if (sy==0) slopeX=1; 27 if (sx==0) slopeY=1; 28 b = bb; 29 30 if (sx<0 || sy<0) negSlope = true; 31 else negSlope = false; 32 33 samePointLine = spl; 34 35 pointSet = new HashSet (); 36 37 uid = Integer.toString(slopeX)+"/"+Integer.toString(slopeY)+"/"+Double.toString(b)+"/"+Boolean.toString(negSlope)+"/"+Boolean.toString(samePointLine); 38 } 39 40 public boolean equals(Line l2){ 41 if (uid==l2.uid) 42 return true; 43 else return false; 44 } 45 46 } 47 48 49 public class Solution { 50 public int maxPoints(Point[] points) { 51 if (points.length==1) return 1; 52 53 Set pSet = new HashSet (); 54 for (int i=0;i lineList = new HashMap (); 57 List uidList = new ArrayList (); 58 for (int i=1;i curPSet = new HashSet (); 60 curPSet.addAll(pSet); 61 for (int j=0;j max)107 max = lineList.get(uidList.get(i)).pointSet.size();108 109 return max;110 111 }112 113 114 public int getGCD(int a, int b){115 int left = a%b;116 while (left!=0){117 a=b;118 b=left;119 left=a%b;120 }121 return b;122 }123 124 125 }