package com.fishercoder.solutions;

import java.util.HashMap;
import java.util.Map;

/**
 * 149. Max Points on a Line
 *
 * Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
 *
 * Example 1:
 * Input: [[1,1],[2,2],[3,3]]
 * Output: 3
 * Explanation:
 * ^
 * |
 * |        o
 * |     o
 * |  o
 * +------------->
 * 0  1  2  3  4
 *
 * Example 2:
 * Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
 * Output: 4
 * Explanation:
 * ^
 * |
 * |  o
 * |     o        o
 * |        o
 * |  o        o
 * +------------------->
 * 0  1  2  3  4  5  6
 *
 * NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
 */
public class _149 {

  /**
   * credits: https://leetcode.com/problems/max-points-on-a-line/discuss/328269/A-Java-solution-with-my-understanding
   */
  public static class Solution1 {
    public int maxPoints(int[][] points) {
      if (points.length < 3) {
        return points.length;
      }
      int max = 0;
      Map<Long, Integer> map = new HashMap<>();
      for (int i = 0; i < points.length; i++) {
        int dup = 1;
        map.clear();
        for (int j = i + 1; j < points.length; j++) {
          int dx = points[j][0] - points[i][0];
          int dy = points[j][1] - points[i][1];
          if (dx == 0 && dy == 0) {
            dup++;
          } else {
            int gcd = getGcd(dx, dy);
            long slope = ((long) (dy / gcd) << 32) + (dx / gcd);
            map.put(slope, map.getOrDefault(slope, 0) + 1);
          }
        }
        max = Math.max(max, dup);
        for (Map.Entry<Long, Integer> entry : map.entrySet()) {
          max = Math.max(max, entry.getValue() + dup);
        }
      }
      return max;
    }

    int getGcd(int a, int b) {
      return b == 0 ? a : getGcd(b, a % b);
    }
  }
}

@@ -82,647 +82,8 @@
 p;%0A%0A
-/**%0A * 149. Max Points on a Line%0A *%0A * Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.%0A *%0A * Example 1:%0A * Input: %5B%5B1,1%5D,%5B2,2%5D,%5B3,3%5D%5D%0A * Output: 3%0A * Explanation:%0A * %5E%0A * %7C%0A * %7C        o%0A * %7C     o%0A * %7C  o%0A * +-------------%3E%0A * 0  1  2  3  4%0A *%0A * Example 2:%0A * Input: %5B%5B1,1%5D,%5B3,2%5D,%5B5,3%5D,%5B4,1%5D,%5B2,3%5D,%5B1,4%5D%5D%0A * Output: 4%0A * Explanation:%0A * %5E%0A * %7C%0A * %7C  o%0A * %7C     o        o%0A * %7C        o%0A * %7C  o        o%0A * +-------------------%3E%0A * 0  1  2  3  4  5  6%0A *%0A * NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.%0A */%0A
 publ
@@ -103,14 +103,18 @@
  %7B%0A%0A
+  
   /**%0A
+  
    *
@@ -234,11 +234,15 @@
 %0A   
+  
 */%0A
+  
   pu
@@ -271,16 +271,20 @@
 tion1 %7B%0A
+    
     publ
@@ -314,24 +314,30 @@
 %5D points) %7B%0A
+      
       if (po
@@ -359,24 +359,32 @@
 ) %7B%0A        
+       
+ 
 return point
@@ -393,24 +393,30 @@
 length;%0A
+      
       %7D%0A
       in
@@ -403,24 +403,30 @@
           %7D%0A
+      
       int ma
@@ -438,16 +438,22 @@
 ;%0A      
+ 
+     
 Map%3CLong
@@ -488,24 +488,30 @@
 %3C%3E();%0A      
+  
+    
 for (int i =
@@ -544,24 +544,32 @@
 ) %7B%0A        
+   
+     
 int dup = 1;
@@ -573,24 +573,32 @@
  1;%0A        
+  
+      
 map.clear();
@@ -598,32 +598,40 @@
 lear();%0A        
+ 
+       
 for (int j = i +
@@ -666,24 +666,34 @@
 %7B%0A          
+       
+   
 int dx = poi
@@ -724,24 +724,34 @@
 ;%0A          
+    
+      
 int dy = poi
@@ -782,24 +782,34 @@
 ;%0A          
+ 
+         
 if (dx == 0 
@@ -838,15 +838,34 @@
     
+     
-dup++;%0A
+       dup++;%0A       
     
@@ -870,16 +870,19 @@
         
+   
 %7D else %7B
@@ -890,24 +890,36 @@
             
+          
+  
 int gcd = ge
@@ -932,16 +932,28 @@
 x, dy);%0A
+            
         
@@ -1009,16 +1009,28 @@
 / gcd);%0A
+            
         
@@ -1083,34 +1083,34 @@
 + 1);%0A          
+  
-%7D%0A
         %7D%0A      
@@ -1095,32 +1095,58 @@
               %7D%0A
+                %7D%0A        
         max = Ma
@@ -1167,24 +1167,32 @@
 p);%0A        
+   
+     
 for (Map.Ent
@@ -1237,32 +1237,42 @@
 ()) %7B%0A          
+         
+ 
 max = Math.max(m
@@ -1312,18 +1312,38 @@
     
-%7D%0A
+        %7D%0A     
       
+ 
 %7D%0A
+      
     
@@ -1364,15 +1364,23 @@
     
-%7D%0A%0A
+    %7D%0A%0A   
     
+ 
 int 
@@ -1398,24 +1398,30 @@
 a, int b) %7B%0A
+      
       return
@@ -1456,16 +1456,22 @@
 b);%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 149