​LeetCode刷题实战587：安装栅栏

class Solution {
  
  class node {
    
    int x,y; 
    public node(int x,int y) {
      this.x=x;
      this.y=y;
    }
  }
  
  private node st;
  
  class mySort implements Comparator<node>{

    @Override
    public int compare(node o1, node o2) {
      // TODO 自动生成的方法存根
      int diff=Cross(st,o1,o2)-Cross(st,o2,o1);
      if(diff==0)
        return dis(st,o1)-dis(st,o2);
      return diff>0?1:-1;
    }
    
  }
  
    public int[][] outerTrees(int[][] points) {
        
      if(points.length<=3) return points;
      
      node[] q=new node[points.length+1];
      node[] arr=new node[points.length];
      st=new node(Integer.MAX_VALUE,Integer.MAX_VALUE);
      
      for(int i=0;i        arr[i]=new node(points[i][0],points[i][1]);
        if(arr[i].y          st.x=arr[i].x; st.y=arr[i].y;
        }
      }
      
      Arrays.parallelSort(arr,new mySort());
      
      int p=arr.length-1;
      while(p>=0 && Cross(st,arr[arr.length-1],arr[p])==0)
        p--;
      for(int l=p+1,r=arr.length-1;l        node tmp=arr[l];
        arr[l]=arr[r];
        arr[r]=tmp;
      }
      
      int top=2;
      q[1]=new node(arr[0].x,arr[0].y);
      q[2]=new node(arr[1].x,arr[1].y);
      
      for(int i=2;i        while(top>1 && Cross(q[top-1],q[top],arr[i])>0)
          top--;
        q[++top]=arr[i];
      }
      
      int[][] ans=new int[top][2];
      for(int i=1;i<=top;i++) {
        ans[i-1][0]=q[i].x;
        ans[i-1][1]=q[i].y;
      }
      
      return ans;
    }
    
    //求叉积，若大于0则表明新的点在直线右侧
    private int Cross(node p1,node p2,node p3) {
      return (p2.x-p1.x)*(p3.y-p2.y)-(p3.x-p2.x)*(p2.y-p1.y);
    }
    
    private int dis(node p1,node p2) {
      return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
    }
}