Java solution(use cos(theta) to tell the directions)


  • 0
    L
    /**
     * Definition for a point.
     * class Point {
     *     int x;
     *     int y;
     *     Point() { x = 0; y = 0; }
     *     Point(int a, int b) { x = a; y = b; }
     * }
     */
    public class Solution {
        public List<Point> outerTrees(Point[] points) {
            List<Point> resTmp=new ArrayList();
            if(points==null||points.length==0) return resTmp;
            if(points.length<4) {
                for(Point pt:points) resTmp.add(pt);
                return resTmp;
            }
            int len=points.length;
    
            boolean []visited=new boolean[len];
            
            Arrays.sort(points,(a,b)->((a.x==b.x)?(a.y-b.y):(a.x-b.x)));
            
            Point start=points[0];
            Point end=new Point(Integer.MIN_VALUE,Integer.MIN_VALUE);
            
            int []v1={0,1};
            int []v2={0,1};
            double []cosAll=new double[len];
            
            while(!(start.x==end.x&&start.y==end.y)){
                Point tmp=null;
                if(end.x==Integer.MIN_VALUE) tmp=start;
                else tmp=end;
                double maxCos=-2.0;
    
                for(int i=0;i<len;i++)
                {
                    if(visited[i]) continue;
                    Point pt=points[i];
                    v2[0]=pt.x-tmp.x;v2[1]=pt.y-tmp.y;
                    if(v2[0]==0&&v2[1]==0) continue;
                    double cos=cosine(v1,v2);
                    cosAll[i]=cos;
                    if(cos>maxCos) {maxCos=cos;}
                }
                end=null;
                for(int i=0;i<len;i++)
                {
                    if(visited[i]) continue;
                    Point pt=points[i];
                    if(Math.abs(cosAll[i]-maxCos)<1e-8) {
                        resTmp.add(pt);
                        visited[i]=true;
                        if(end!=null){
                            if(distance2(pt,tmp)>distance2(end,tmp)) end=pt;
                        }
                        else end=pt;
                            
                        v1[0]=pt.x-tmp.x;
                        v1[1]=pt.y-tmp.y;
                    }
                }
            }
            return resTmp;
        }
        
        private double cosine(int []v1,int []v2){
            return (v1[0]*v2[0]+v1[1]*v2[1])/Math.sqrt(v1[0]*v1[0]+v1[1]*v1[1])/Math.sqrt(v2[0]*v2[0]+v2[1]*v2[1]);
        }
        
        private int distance2(Point a,Point b){
            return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
        }
        
    }
    
    

Log in to reply
 

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