# Java Solution 42ms

• ``````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){
else{
while(res.size() > 1 && comp.compare(res.get(res.size()-2), res.get(res.size() - 1), p) < 0){
res.remove(res.size() - 1);
}
}
}
// 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) {