# Using divide and conquer

• ``````public List<Point> outerTrees(Point[] points) {
List<Point> pp = new ArrayList<>();
for (Point p : points){
}
helper(pp,true);
helper(pp, false);
return new ArrayList<>(ans);
}

Set<Point> ans = new HashSet<>();
private void helper(List<Point> points, boolean calcuConvex){
if (points.size() == 0) return;
Collections.sort(points, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return o1.x != o2.x ? o1.x - o2.x : o1.y - o2.y;
}
});
int fir = 0;
int lst = points.size() - 1;

if (points.size() == 2)
return;

// oneLine
boolean isLine = true;
for (int i = 0; i < points.size(); i++) {
if (i == fir || i == lst)
continue;
if (calcuTriangle(points.get(fir), points.get(lst), points.get(i)) != 0) {
isLine = false;
break;
}
}
if (isLine) {
return;
}

int maxIndex = -1;
int max = 0;
for (int i = 0; i < points.size(); i++) {
if (i == fir || i == lst)
continue;
if (calcuConvex && calcuTriangle(points.get(fir), points.get(lst), points.get(i)) > max) {
maxIndex = i;
max = calcuTriangle(points.get(fir), points.get(lst), points.get(i));
}
if (!calcuConvex && -calcuTriangle(points.get(fir), points.get(lst), points.get(i)) > max) {
maxIndex = i;
max = -calcuTriangle(points.get(fir), points.get(lst), points.get(i));
}
}

if (maxIndex == -1) {
return;
}

List<Point> c1 = new ArrayList<>();
split(fir, maxIndex, points, c1, calcuConvex);
helper(c1,calcuConvex);

List<Point> c2 = new ArrayList<>();
split(lst, maxIndex, points, c2, !calcuConvex);
helper(c2,calcuConvex);
}

private void split(int a1, int a2, List<Point> points, List<Point> part1, boolean isConvex) {
for (int i = 0; i < points.size(); i++) {
if (i == a1 || i == a2) {
continue;
}
if (isConvex && calcuTriangle(points.get(a1), points.get(a2), points.get(i)) >= 0) {
}

if (!isConvex && calcuTriangle(points.get(a1), points.get(a2), points.get(i)) <= 0) {