LeetCode - Algorithms - 1232. Check If It Is a Straight Line

Problem

1232. Check If It Is a Straight Line

similar question

Java

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    private boolean isColine(int x1, int y1, int x2, int y2, int x3, int y3) {
        int a = (y3 - y2) * (x3 - x1);
        int b = (y3 - y1) * (x3 - x2);
        return a == b;
    }

    public boolean checkStraightLine(int[][] coordinates) {
        final int N = coordinates.length;
        boolean b;
        for (int i = 0; i < N - 2; i++) {
            b = isColine(coordinates[i][0], coordinates[i][1], coordinates[i + 1][0], coordinates[i + 1][1], coordinates[i + 2][0], coordinates[i + 2][1]);
            if (b == false)
                return false;
        }
        return true;
    }
}

Submission Detail

  • 79 / 79 test cases passed.
  • Runtime: 1 ms, faster than 22.67% of Java online submissions for Check If It Is a Straight Line.
  • Memory Usage: 41 MB, less than 6.80% of Java online submissions for Check If It Is a Straight Line.

Computational geometry method

© Copyright 2002-2020, Robert Sedgewick and Kevin Wayne.

keys

  • Shoelace formula, also known as Gauss’s area formula
  • vertices must listed in clockwise(or counterclockwise, increasing order of polar angle) order
  • CCW: Given three points a, b, and c, is a→b→c a counterclockwise turn? Determinant (or cross product) gives 2x signed area of planar triangle.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.Comparator;
import java.util.Arrays;

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        final int N = coordinates.length;
        Point2D[] a = new Point2D[N];
        for (int i = 0; i < N; i++) {
            a[i] = new Point2D(coordinates[i][0], coordinates[i][1]);
        }
        Arrays.sort(a);
        Arrays.sort(a, 1, N, a[0].polarOrder());
        int A = a[N - 1].x() * a[0].y() - a[0].x() * a[N - 1].y();
        for (int i = 0; i < N - 1; i++) {
            A += a[i].x() * a[i + 1].y() - a[i + 1].x() * a[i].y();
        }
        return A == 0;
    }
}

final class Point2D implements Comparable<Point2D> {
    private final int x;
    private final int y;

    public Point2D(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int x() {
        return x;
    }

    public int y() {
        return y;
    }

    public static int ccw(Point2D a, Point2D b, Point2D c) {
        int area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
        if (area2 < 0) return -1;
        else if (area2 > 0) return +1;
        else return 0;
    }

    public int compareTo(Point2D that) {
        if (this.y < that.y) return -1;
        if (this.y > that.y) return +1;
        if (this.x < that.x) return -1;
        if (this.x > that.x) return +1;
        return 0;
    }

    public Comparator<Point2D> polarOrder() {
        return new PolarOrder();
    }

    private class PolarOrder implements Comparator<Point2D> {
        public int compare(Point2D q1, Point2D q2) {
            int dx1 = q1.x - x;
            int dy1 = q1.y - y;
            int dx2 = q2.x - x;
            int dy2 = q2.y - y;

            if (dy1 >= 0 && dy2 < 0) return -1;
            else if (dy2 >= 0 && dy1 < 0) return +1;
            else if (dy1 == 0 && dy2 == 0) {
                if (dx1 >= 0 && dx2 < 0) return -1;
                else if (dx2 >= 0 && dx1 < 0) return +1;
                else return 0;
            } else return -ccw(Point2D.this, q1, q2);
        }
    }
}

Submission Detail

  • 79 / 79 test cases passed.
  • Runtime: 6 ms, faster than 9.07% of Java online submissions for Check If It Is a Straight Line.
  • Memory Usage: 38.8 MB, less than 6.80% of Java online submissions for Check If It Is a Straight Line.