1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 596 - The Incredible Hull
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=537
*
* @author Evgeni Pavlidis
* @version 1.0, 06/02/2010
*
* Method : Comp. Geometry - Convex Hull - Jarvis March
* Status : Accepted
* Runtime: 0.160
*/

/* just ignore polygon structures and compute
convex hull for all points */

import java.util.*;
import java.io.*;

class Main {

public static final int X = 0;
public static final int Y = 1;
public static final int MAX = 50000;

private static int[][] point;
private static int points;


private static long crossProduct(int[] m, int[] a, int[] b)
{
return ((a[X] - m[X])*(b[Y] - m[Y]) - (a[Y] - m[Y])*(b[X] - m[X]));
}

private static int findMin()
{
int maxX = Integer.MIN_VALUE;
int minY = Integer.MAX_VALUE;
int save = 0;

for(int p = 0; p < points; p++)
if(point[p][X] > maxX || (point[p][X] == maxX && point[p][Y] < minY))
{
save = p;
maxX = point[p][X];
minY = point[p][Y];
}

return save;
}

private static int dist(int[] a, int[] b)
{
int tmp, result;

tmp = a[X] - b[X];
result = tmp*tmp;
tmp = a[Y] - b[Y];
result += tmp*tmp;

return result;
}

private static List<Integer> convexHull(int s)
{
List<Integer> result = new ArrayList<Integer>();

List<Integer> list = new ArrayList<Integer>();
for(int p = 0; p < points; p++)
list.add(p);

int start, end, minDist, dist, tmp;
long crossProduct;
start = s;

do
{
result.add(start);
end = list.get(0);

if(start == end)
end = list.get(1);

minDist = dist(point[start], point[end]);

for(int i = 1; i < list.size(); i++)
if(end != list.get(i) && start != list.get(i))
{
crossProduct = crossProduct(point[start], point[end], point[list.get(i)]);
if(crossProduct < 0 || (crossProduct == 0 && dist(point[start], point[list.get(i)]) <= minDist) )
end = list.get(i);
}

list.remove(new Integer(end));

start = end;

}while(end != s );

return result;
}


public static void main(String...args)
{
Scanner sc = new Scanner(System.in);

String sample = "", input;

points = 0;
point = new int[MAX][2];

while(true)
{
input = sc.next();

// end of samples or new sample
if(!input.equals("P"))
{
// if not first sample, process and output the last one
if(!sample.equals(""))
{
System.out.println(sample + " convex hull:");

List<Integer> list = convexHull(findMin());

for(int p: list)
System.out.print(" (" + point[p][X] + "," + point[p][Y]+ ")");
System.out.println();

}

// (re)init
point = new int[MAX][2];
points = 0;

if(input.equals("S"))
{
sample = sc.nextLine().trim();
continue;
}
else
break;
}

int c = sc.nextInt();
for(int p = 0; p < c; p++)
{
point[points][X] = sc.nextInt();
point[points][Y] = sc.nextInt();
points++;
}
}


}
}