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], 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);
    }
  }
}

@@ -973,16 +973,26 @@
 gth %3C 3)
+ %7B%0A       
  return 
@@ -1006,16 +1006,24 @@
 length;%0A
+      %7D%0A
       in
@@ -1271,17 +1271,31 @@
 ts%5Bi%5D%5B0%5D
-,
+;%0A          int
  dy = po
@@ -1354,16 +1354,30 @@
 dy == 0)
+ %7B%0A           
  dup++;%0A
@@ -1385,16 +1385,18 @@
         
+ %7D
  else %7B%0A
@@ -1675,16 +1675,18 @@
 rySet())
+ %7B
 %0A       
@@ -1729,24 +1729,34 @@
 e() + dup);%0A
+        %7D%0A
       %7D%0A    

fix build