几天来，我一直在为这个问题绞尽脑汁……我看不出我的算法可能遗漏了什么。这就是这里的问题。
从我收集到的信息中，我以某种循环的 ccw 顺序获得积分。因此，我实现了一个 graham 扫描版本，通过确保它使用始终提供右转的点来寻找凸包。
我的算法适用于所有给定的测试输入和我可以提出的所有输入，但它不会被在线法官接受，这是作业“完成”所必需的。
无论如何，这是我的代码，如果有人能找到我所缺少的东西，我将永远欠你的债。
import java.util.Scanner;
import java.util.Vector;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
public Main() {}
public void handlePoints(Point[] points) throws Exception {
int m = 1;
Vector<Point> convexHull = new Vector<Point>();
// This is THE ONLY gaurunteed point to be in the hull - and it is the lowest left point so that's ok.
convexHull.add(points[0]);
// Can be removed if ill-suited.
convexHull.add(points[1]);
for (int i = 2; i < points.length; i++) {
// Find the next valid point on the hull.
while (counterClockWise(convexHull.elementAt(m-1), convexHull.elementAt(m), points[i]) <= 0) {
convexHull.removeElementAt(m);
if (m > 1) {
m -= 1;
}
// All points are colinear
else if (i == points.length - 1) {
break;
}
else {
convexHull.add(points[i]);
i++;
}
}
convexHull.add(points[i]);
m++;
}
if (convexHull.size() <= 3) {
throw new Exception();
}
String test = "" + convexHull.size() + '\n';
for (Point p : convexHull) {
test += p.x + " " + p.y + '\n';
}
System.out.print(test);
}
// Simply calculated whether or not the 3 points form a countedClockWise turn.
public int counterClockWise(Point p1, Point p2, Point p3) {
return ((p2.x - p1.x) * (p3.y - p1.y)) - ((p2.y - p1.y) * (p3.x - p1.x));
}
// Rearranges the array to maintain its order but be started and ended by the point with the lowest y value
private static Point[] moveLowestToFront(Point[] array) {
// Rearrange for y:
int lowestY = 99999;
int lowestIndex = 0;
for (int i = 0; i < array.length; i++) {
if (array[i].y < lowestY) {
lowestY = array[i].y;
lowestIndex = i;
}
}
// Scan through again to see if there are any competing low-y values.
int lowestX = 99999;
for (int i = 0; i < array.length; i++) {
if (array[i].y == lowestY) {
if (array[i].x < lowestX) {
lowestX = array[i].x;
lowestIndex = i;
}
}
}
Point[] rearrangedPoints = new Point[array.length];
int j = 0;
// Take from low to end cutting off repeated start point.
for (int i = lowestIndex; i < array.length - 1; i++) {
rearrangedPoints[j] = array[i];
j++;
}
// Throw the remaining and put them at the end.
for (int i = 0; i < lowestIndex; i++) {
rearrangedPoints[j] = array[i];
j++;
}
// End the array with the repeated first point.
rearrangedPoints[array.length - 1] = array[lowestIndex];
return rearrangedPoints;
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
Main convexHullFinder = new Main();
int numDataSets = sc.nextInt();
System.out.println(numDataSets);
for (int z = 0; z < numDataSets; z++) {
int numPoints = sc.nextInt();
Vector<Point> points = new Vector<Point>();
// Read in all the points for this set.
points.add(new Point(sc.nextInt(), sc.nextInt()));
int j = 1;
for (int i = 1; i < numPoints; i++) {
Point p = new Point(sc.nextInt(), sc.nextInt());
// Remove repeated points.
if (p.x < 0 || p.y < 0) {
throw new Exception();
}
if ( (p.x == points.elementAt(j-1).x) && (p.y == points.elementAt(j-1).y) ) {}
else {
points.add(p);
j++;
}
}
Point[] reducedPoints = points.toArray(new Point[points.size()]);
// Rearrange the set to start and end on the lowest Y point.
reducedPoints = moveLowestToFront(reducedPoints);
if (numPoints >= 3) {
convexHullFinder.handlePoints(reducedPoints);
}
else {
throw new Exception();
}
try {
System.out.println(sc.nextInt());
}
catch (Exception e) {
}
}
}
}
class Point {
public int x;
public int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}