/* * Given a list of a convex polygon's vertices as integer x and y pairs, * not necessarily in any order, order them as they would be walking the * polygon clockwise starting with the left-most (x) vertex * (and bottom-most of the left-most, if there is more than one). * You may assume no three vertices of the polygon are colinear, * each polygon has at least three vertices, and no vertex is repeated in * the list. * * Parke Godfrey * 11 September 2008 */ import java.util.Scanner; import java.io.PrintStream; import java.util.Arrays; class Vertex implements Comparable { public int x; public int y; public int compareTo(Object obj) { Vertex other = (Vertex) obj; if (this.x < other.x) { return -1; } else if (this.x > other.x) { return 1; } else { if (this.y < other.y) { return -1; } else if (this.y > other.y) { return 1; } else { return 0; } } } } public class WalkPolygon { private static boolean above(Vertex v, Vertex s, int run, int rise) { if (rise == 0) { if (v.y > s.y) { return true; } else { return false; } } else { if (((v.y - s.y) * run) > ((v.x - s.x) * rise)) { return true; } else { return false; } } } public static void main(String[] args) { Scanner input = new Scanner(System.in); PrintStream output = System.out; int trials = input.nextInt(); output.println(trials); while (trials-- > 0) { // Read in a list of vertices for the polygon. int last = input.nextInt(); output.println(last); Vertex[] vert = new Vertex[last]; for (int v = 0; v < last; v++) { vert[v] = new Vertex(); vert[v].x = input.nextInt(); vert[v].y = input.nextInt(); } // Sort the vertices. Arrays.sort(vert); // Find the run and rise from left-most lower to right-most // upper. Call this the diagonal. int run = vert[last-1].x - vert[0].x; int rise = vert[last-1].y - vert[0].y; // Print the first vertex. output.print(vert[0].x); output.print(" "); output.println(vert[0].y); // Print vertices above the diagonal in order going right. for (int v = 1; v < last-1; v++) { if (above(vert[v], vert[0], run, rise)) { output.print(vert[v].x); output.print(" "); output.println(vert[v].y); } } // Print the last vertex. output.print(vert[last-1].x); output.print(" "); output.println(vert[last-1].y); // Print vertices below the diagonal in order going left. for (int v = last-2; v > 0; v--) { if (!above(vert[v], vert[0], run, rise)) { output.print(vert[v].x); output.print(" "); output.println(vert[v].y); } } } } }