149. Max Points on a Line

Description

Here

Solution

这道题有多个陷阱：

1. 斜率不能用double，整数范围内精度不足

处理方法就是用gcd，化简成最简分数，然后两个整数用一个long来存， 这里还有一个贼骚的gcd写法：

 private static int gcd(int a, int b) {
    System.out.println("\ta = " + a + ", b = " + b);
    if (Math.abs(b) > Math.abs(a)) {
      return gcd(b, a);
    }
    if (b == 0) {
      return a;
    }

    return gcd(b, a % b);
  }
  /**
  * [-18, 12]
  * a = -18, b = 12
  * a = 12, b = -6
  * a = -6, b = 0
  * gcd = -6
  * [18, -12]
  * a = 18, b = -12
  * a = -12, b = 6
  * a = 6, b = 0
  * gcd = 6
  * [18, 12]
  * a = 18, b = 12
  * a = 12, b = 6
  * a = 6, b = 0
  * gcd = 6
  * [-18, -12]
  * a = -18, b = -12
  * a = -12, b = -6
  * a = -6, b = 0
  * gcd = -6
  */
  public static void main(String[] args) {
    System.out.println(Arrays.toString(new int[] {-18, 12}));
    System.out.println("gcd = " + gcd(-18, 12));
    System.out.println(Arrays.toString(new int[] {18, -12}));
    System.out.println("gcd = " + gcd(18, -12));
    System.out.println(Arrays.toString(new int[] {18, 12}));
    System.out.println("gcd = " + gcd(18, 12));
    System.out.println(Arrays.toString(new int[] {-18, -12}));
    System.out.println("gcd = " + gcd(-18, -12));
  }

这个解法保证了a/gcd 与 b/gcd如果有一个是负数，则负数会在b上。