题目：https://leetcode-cn.com/problems/erect-the-fence/
代码：
class Solution {
public int[][] outerTrees(int[][] points) {
//list保存使用到的点的下标
List<Integer> list = new ArrayList<>();
int first = this.findFirst(points);//起点
int cur = first;//当前点
int next;//下一个点
//每次寻找的最小角度
double minAngle = 0;
do {
//找到的点加到结果中
if (!list.contains(cur)) {
list.add(cur);
}
//开始寻找下一个点
//下一个点的默认信息
next = first;
double[] nextPolar = new double[]{Double.MAX_VALUE, 2 * Math.PI};
//遍历每一个点
for (int i = 0; i < points.length; i++) {
if (cur==i) {
//当前点跳过
continue;
}
//计算每一个点基于当前点的极坐标
double[] polar = this.polarCoordinate(points[cur], points[i]);
if (polar[1] >= minAngle) {
//满足最小角度的条件，取符合条件中角度最小，如果角度相等，取长度最短的值
if (polar[1] < nextPolar[1] || (polar[1] == nextPolar[1] && polar[0] < nextPolar[0])) {
nextPolar = polar;
next = i;
}
}
}
//成功找到下一个点，更新最小角度
minAngle = nextPolar[1];
//更新当前点信息，继续循环找下一个点
cur = next;
} while (next != first);
//返回结果
int[][] res = new int[list.size()][2];
for (int i = 0; i < list.size(); i++) {
res[i] = points[list.get(i)];
}
return res;
}
/**
* 查找第一个节点，取所有值中y轴的值最小的点作为第一个节点
*
* @param points
* @return
*/
private int findFirst(int[][] points) {
int min = 0;
for (int i = 1; i < points.length; i++) {
if (points[i][1] < points[min][1]) {
min = i;
}
}
return min;
}
/**
* 获取p点基于o点的极坐标
* 返回一个数组，0为长度r，1为角度angle（用π标识的弧形角）
*
* @param o
* @param p
* @return
*/
private double[] polarCoordinate(int[] o, int[] p) {
double x = p[0] - o[0];
double y = p[1] - o[1];
//使用公式计算极坐标
double r = Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
double angle = 0;
if (x > 0 && y >= 0) {
//第一象限
angle = Math.atan(y / x);
} else if (x < 0) {
//第二、三象限
angle = Math.atan(y / x) + Math.PI;
} else if (x > 0 && y < 0) {
//第四象限
angle = Math.atan(y / x) + Math.PI * 2;
} else if (x == 0 && y > 0) {
//y轴正轴
angle = Math.PI / 2;
} else if (x == 0 && y < 0) {
//y轴负轴
angle = Math.PI / 2 * 3;
} else if (x == 0 && y == 0) {
//原点
angle = 0;
}
return new double[]{r, angle};
}
}
我的思路是，想象有一根跟x轴平行的无限长的绳子，以所有点的最下方作为起点（即y轴值最小的点），拽着无限长的绳子的末端逆时针旋转一周，每个绳子接触到的点就是答案所包含的点，当绳子再次回到起点的时候，就围成了一个闭合图形。这个时候答案就找到了。
如图，如果在绳子上的每个点都做一条水平线的话，那么下一个点的绳子与水平线的夹角一定会从0开始慢慢变大，直到360度（即旋转一圈）
这个时候我们发现，如果以每个绳子的点为原点做一个极坐标，那么下一个点的坐标位置的角度就是我们绳子基于水平线旋转扫过的角度。我们遍历计算所有的点，取旋转角度最小的一个点作为下一个点。
最终当我们的绳子回到起点的时候，闭合图形就行程了。这个时候答案就找到了。具体的实现参考代码及注释，至于为什么绳子这样绕一圈就是答案，我想不到如何解释，可能这就是生活常识吧，哈哈，自己拿根绳子试一下。
看完官方题解之后，其实我的这个思路就是凸包法，我用来确定凸包的方法是计算极坐标的角度，而官方题解使用的是向量积。小弟我多年没做过几何数学题了，说实话，看不懂~~~
