题目链接:安装栅栏
简单的求凸包上的点的题目
注意对于最后的一些点,如果最后的几个点到起点位置是共线的,需要将这些点反转.
class Solution {

public int[][] outerTrees(int[][] points)
{
if (points.length < 4)
{
return points;
}
if (isOneLine(points))
{
return points;
}

int[] minPoint = points[0];
for (int i = 1; i < points.length; i++) { if (minPoint[1] > points[i][1])
{
minPoint = points[i];
} else if (minPoint[1] == points[i][1] && minPoint[0] > points[i][0])
{
minPoint = points[i];
}
}

final int[] firstPoint = minPoint;
Arrays.sort(points, new Comparator<int[]>() {

@Override
public int compare(int[] o1, int[] o2)
{
final int calcResult = threePointLineDegree(firstPoint, o1, firstPoint, o2);
if (calcResult > 0)
{
return -1;
} else if (calcResult == 0)
{
if (lineDistancePow(firstPoint, o1) < lineDistancePow(firstPoint, o2))
{
return -1;
}
return 1;
} else
{
return 1;
}
}
});

// 极角相等，需要按照举例从小到大排序，但是排序后，有可能最后一条边有几个点共线的情况，需要进行反转
points = reverseLast(points);
final Stack stack = new Stack();
stack.push(0);
stack.push(1);
stack.push(2);

for (int i = 3; i < points.length; i++) { while (true) { final int judge = stack.pop(); final int[] judgePoint = points[judge]; final int[] basePointPoint = points[stack.peek()]; final int[] nextPoint = points[i]; if (threePointLineDegree(basePointPoint, judgePoint, judgePoint, nextPoint) >= 0)
{
stack.push(judge);
break;
}
}
stack.push(i);
}

final int[][] result = new int[stack.size()][2];
int cnt = 0;
while (!stack.isEmpty())
{
result[cnt] = points[stack.pop()];
cnt++;
}
return result;
}

private int[][] reverseLast(int[][] sortedPoints)
{
final int length = sortedPoints.length;
int lastLineStartIndex = -1;
for (int i = sortedPoints.length - 1; i >= 0; i--)
{
if (threePointLineDegree(sortedPoints[0], sortedPoints[i], sortedPoints[0], sortedPoints[i - 1]) != 0)
{
lastLineStartIndex = i;
break;
}
}
if (lastLineStartIndex == length - 1)
{
return sortedPoints;
}
int changeIndex = lastLineStartIndex;
final int[][] newArray = Arrays.copyOf(sortedPoints, sortedPoints.length);
for (int i = length - 1; i >= lastLineStartIndex; i--)
{
newArray[changeIndex++] = sortedPoints[i];
}
return newArray;
}
private boolean isOneLine(int[][] points)
{
for (int i = 1; i < points.length - 1; i++)
{
if (threePointLineDegree(points[0], points[i], points[0], points[i + 1]) == 0)
{
continue;
}
return false;
}
return true;
}

private int lineDistancePow(int[] point1, int[] point2)
{
return (int) (Math.pow(point2[0] - point1[0], 2) + Math.pow(point2[1] - point1[1], 2));
}

private int threePointLineDegree(int[] point1, int[] point2, int[] point3, int[] point4)
{
final int[] vector12 = new int[]
{ point2[0] - point1[0], point2[1] - point1[1] };
final int[] vector34 = new int[]
{ point4[0] - point3[0], point4[1] - point3[1] };
return vector12[0] * vector34[1] - vector12[1] * vector34[0];
}

}