Google – Find Triangle

Google – Find Triangle
给一堆点，找出一个三角形，条件是这个三角形里没有其他任何点。
[Solution]
找最值，比如y最大或者最小的三个点，或者x最大/最小的三个点。只要最大/小的三个点不在一条直线上，就能保证这个三角形里没有其他任何点。
[Time]
O(n) Average, O(n^2) worst case when there is no such triangle.
Or, sort first, then O(nlogn) time is guaranteed.

public List<Point> findTriangle(List<Point> points) {

  List<Point> result = new ArrayList<>();

  if (points == null || points.isEmpty()) {

    return result;

  }

   

  Point fstMin = null;

  Point secMin = null;

   

  for (Point point : points) {

    if (fstMin == null || point.y < fstMin.y) {

      secMin = fstMin;

      fstMin = point;

    }

    else if (secMin == null || point.y < secMin.y) {

      secMin = point;

    }

  }

   

  boolean[] isVisited = new boolean[points.size()];

  int cnt = 2;

  while (cnt < points.size()) {

    Point thirdMin = null;

    int idx = -1;

    for (int i = 0; i < points.size(); i++) {

      if (points[i].y >= secMin.y && points[i].y < thirdOne.y && !isVisited[i]) {       

        idx = i;

        thirdOne = point;

      }

    }

     

    if (!sameLine(fstMin, secMin, thirdMin)) {

      result.add(fstMin);

      result.add(secMin);

      result.add(thirdMin);

      break;

    }

    else {

      isVisited[idx] = true;

      cnt++;

    }

  }

   

  return result;

}

 

private boolean sameLine(Point a, Point b, Point c) {

  double k1 = (b.y - a.y) / (b.x - a.x);

  double k2 = (c.y - b.y) / (c.x - b.x);

   

  return k1 == k2;

}

Read full article from Google – Find Triangle