Java Solution 42ms


  • 0
    F
    class PComp implements Comparator<Point> {
    
        Point p;
    
        public PComp(Point p){
            this.p = p;
        }
    
        @Override
        public int compare(Point o1, Point o2) {
            long dx1 = 1L * o1.x - 1L * p.x;
            long dy1 = 1L * o1.y - 1L * p.y;
            long dx2 = 1L * o2.x - 1L * p.x;
            long dy2 = 1L * o2.y - 1L * p.y;
            long left = dx2 * dy1;
            long right = dx1 * dy2;
            return left == right ? Long.compare(dx1 * dx1 + dy1 * dy1, dx2 * dx2 + dy2 * dy2) : Long.compare(left, right);
        }
    
        public int compare(Point o1, Point o2, Point o3) {
            long dx1 = 1L * o2.x - 1L * o1.x;
            long dy1 = 1L * o2.y - 1L * o1.y;
            long dx2 = 1L * o3.x - 1L * o2.x;
            long dy2 = 1L * o3.y - 1L * o2.y;
            long left = dx1 * dy2;
            long right = dx2 * dy1;
            return Long.compare(left, right);
        }
    
    }
    
    public class Solution {
        public List<Point> outerTrees(Point[] points) {
            Point bl = null;
            for(Point p : points){
                if(bl == null) bl = p;
                else if(p.y < bl.y || p.y == bl.y && p.x < bl.x){
                    bl = p;
                }
            }
            if(bl == null) return new ArrayList<Point>();
            PComp comp = new PComp(bl);
            Arrays.sort(points, comp);
            List<Point> res = new Stack<>();
            for(Point p : points){
                if(res.size() < 2) res.add(p);
                else{
                    while(res.size() > 1 && comp.compare(res.get(res.size()-2), res.get(res.size() - 1), p) < 0){
                        res.remove(res.size() - 1);
                    }
                    res.add(p);
                }
            }
    // The last edge is traversed outward, thus missing some vertices, need to find them back.
            if(res.size() != points.length) {
                int i = points.length - 2;
                Point last = points[points.length - 1];
                while (i >= 0) {
                    if (comp.compare(bl, points[i], last) == 0) {
                        res.add(points[i]);
                        i--;
                    } else {
                        break;
                    }
                }
            }
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.