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

• ``````/**
* 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) {
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) {
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);
}

}

``````

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