Я уже несколько дней ломаю голову над этой проблемой... Я не вижу, чего может не хватать в моем алгоритме. Это проблема здесь.
Из того, что я понял, я получаю очки в несколько круговом порядке против часовой стрелки. Поэтому я реализовал версию сканирования Грэма, которая выполняет поиск выпуклой оболочки, гарантируя, что она использует точки, которые всегда дают повороты вправо.
Мой алгоритм работает для всех входных данных теста и всех входных данных, которые я могу для него придумать, но он просто не будет принят онлайн-судьей, что требуется для того, чтобы задание было «завершенным».
В любом случае, вот мой код. Я буду вечно у вас в долгу, если кто-нибудь сможет найти то, что мне не хватает.
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;
}
}
homework
, он объявлен устаревшим. - person Brian   schedule 18.12.2012