1. 

/**
* ACM Training 2009
* ACM Problem #ICPC NWERC Problem I
*
* @author Felix Dietrich
Kevin Kratzer
Dennis Wilfert
* @version 1.0, 11/15/2009
*
* Methode: Point sorting by polar coordinates
* Status : Accepted
* Runtime:
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=13&page=show_contest&contest=240
*/

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main
{
public static Point firstPoint;

// point class
//
public static class Point implements Comparable<Point>
{
public int y;
public int x;
public int index;

public Point(int x2, int y2, int index)
{
this.x = (int) x2;
this.y = (int) y2;
this.index = index;
}

public double angle()
{
return Math.atan2((double) (y - firstPoint.y), (double) (x - firstPoint.x));
}

public double size()
{
return Math.sqrt((long) (x - firstPoint.x) * (long) (x - firstPoint.x) + (long) (y - firstPoint.y) * (long) (y - firstPoint.y));
}

@Override
public String toString()
{
return String.format("[%d %d]", x, y);
}

@Override
public int compareTo(Point p2)
{
if (Math.abs(this.angle() - p2.angle()) < 1e-9)
if (this.size() < p2.size())
return -1;
else if (this.size() > p2.size())
return 1;
else
return 0;
if (this.angle() < p2.angle())
return -1;
return 1;
}
}

public static void main(String... as) throws IOException
{
Scanner sc;
sc = new Scanner(System.in);
int points;
int x, y;
Point tempPoint;
Point pWithLowestY;
StringBuffer sb;
List<Point> polygonPoints = new ArrayList<Point>();
List<Point> reversed = new ArrayList<Point>();

// number of testcases
int cases = sc.nextInt();

for (int k = 0; k < cases; k++)
{
// prepare new testcase
polygonPoints.clear();
pWithLowestY = null;

// start testcase

points = sc.nextInt();

// read in points
for (int p = 0; p < points; p++)
{
x = sc.nextInt();
y = sc.nextInt();
//System.out.print(x + ", " + y + ",");
tempPoint = new Point(x, y, p);

if (pWithLowestY == null)
pWithLowestY = tempPoint;
else if (pWithLowestY.y > tempPoint.y || (pWithLowestY.y == tempPoint.y && pWithLowestY.x > tempPoint.x))
pWithLowestY = tempPoint;

polygonPoints.add(tempPoint);
}

// move the point with lowest y coordinate to index 0
Collections.swap(polygonPoints, 0, polygonPoints.indexOf(pWithLowestY));

// save the first point
firstPoint = pWithLowestY;

// sort points by polar coordinate angle
Collections.sort(polygonPoints);

int i;

// at the end, polygon points with the same angle are sorted in
// exactly the reverse order.
reversed.clear();
for(i=polygonPoints.size()-1; i>0; i--)
{
if(Math.abs(polygonPoints.get(i).angle() - polygonPoints.get(i-1).angle())>1e-9)
break;
reversed.add(polygonPoints.get(i));
}
reversed.add(polygonPoints.get(i));

polygonPoints.removeAll(reversed);

sb = new StringBuffer();
// print the polygon points
for (Point p : polygonPoints)
{
sb.append(p.index);
sb.append(" ");
}
// and the reversed tail
for (Point p : reversed)
{
sb.append(p.index);
sb.append(" ");
}
sb.deleteCharAt(sb.length() - 1);

System.out.println(sb.toString());
}
}

/**
* Calculates the cross product between the three given points.
*
* @return sth. < 0 if the direction p0->p1->p2 is "concave"
*/
public static double ccw(Point p0, Point p1, Point p2)
{
return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}
}

2.

/**
* ACM Training 2009
* ACM Problem #ICPC NWERC Problem I
*
* @author Felix Dietrich
* @version 1.0, 11/15/2009
*
* Methode: Midpoint!, Point sorting by polar coordinates
* Status : Accepted
* Runtime:
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=13&page=show_contest&contest=240
*/

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main
{
public static Point firstPoint;

public static class Point implements Comparable<Point>
{
public double y;
public double x;
public int index;

public Point(double x2, double y2, int index)
{
this.x = x2;
this.y = y2;
this.index = index;
}

public double angle()
{
return Math.atan2((double) (y - firstPoint.y)+1.23e-7, (double) (x - firstPoint.x)+4.56e-7);
}

public double size()
{
return Math.sqrt((long) (x - firstPoint.x) * (long) (x - firstPoint.x) + (long) (y - firstPoint.y) * (long) (y - firstPoint.y));
}

@Override
public String toString()
{
return String.format("[%d %d]", (int)x, (int)y);
}

@Override
public int compareTo(Point p2)
{
if (this.angle() < p2.angle())
return -1;
return 1;
}
}

public static void main(String... as) throws IOException
{
Scanner sc;
sc = new Scanner(System.in);
int points;
int x, y;
Point tempPoint;
Point pWithLowestY;
double mx, my;
StringBuffer sb;
List<Point> polygonPoints = new ArrayList<Point>();

// number of testcases
int cases = sc.nextInt();

for (int k = 0; k < cases; k++)
{
// prepare new testcase
polygonPoints.clear();
pWithLowestY = null;

// start testcase

points = sc.nextInt();

mx = 0;
my = 0;
// read in points
for (int p = 0; p < points; p++)
{
x = sc.nextInt();
y = sc.nextInt();

// calc the mid point of all polygon points
mx += (double)x/(double)points;
my += (double)y/(double)points;
tempPoint = new Point(x, y, p);

if (pWithLowestY == null)
pWithLowestY = tempPoint;
else if (pWithLowestY.y > tempPoint.y || (pWithLowestY.y == tempPoint.y && pWithLowestY.x > tempPoint.x))
pWithLowestY = tempPoint;

polygonPoints.add(tempPoint);
}

// save the mid point
firstPoint = new Point(mx, my, 0);

// sort points by polar coordinate angle relative to the mid point
Collections.sort(polygonPoints);

sb = new StringBuffer();
for (Point p : polygonPoints)
{
sb.append(p.index);
sb.append(" ");
}
sb.deleteCharAt(sb.length() - 1);

System.out.println(sb.toString());
}
}

/**
* Calculates the cross product between the three given points.
*
* @return sth. < 0 if the direction p0->p1->p2 is "concave"
*/
public static double ccw(Point p0, Point p1, Point p2)
{
return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}
}

3. F# von Felix Dietrich - Programm

(**
F# Solution to Problem I - Polygons
of the NWERC ICPC 2009

Author: Felix Dietrich
*)

//requires
open System
open Solver

let filename = "..\\..\\I.in"

let strToNum line =
match line with
| str when ((string)str).Length > 0 -> System.Int32.Parse(str)
| _ -> 0

// read all lines out of the file, skipping the empty ones
(*
let readProblem inFile = Seq.delay(fun () ->
let file = System.IO.File.OpenText(inFile)
seq {
while not file.EndOfStream do
let line = file.ReadLine()
match line with
| "" -> None |> ignore
| s -> yield s
})
*)
let readProblem inFile =
let file = System.IO.File.OpenText(inFile)
[
while not file.EndOfStream do
let line = file.ReadLine()
match line with
| "" -> None |> ignore
| s -> yield s
]

// get problem count and problems out of the file
let (problemCount,problems) =
let lines = readProblem(filename)
let count = strToNum (Seq.nth 0 lines)
(count, lines |> Seq.skip 1 |> Seq.truncate count)

Console.WriteLine("problem count: " + problemCount.ToString());


let time = DateTime.Now

// map all problems on the problem solver
let c = Seq.toList problems
let solutions = problems |> Seq.map(fun prob -> (new PolygonSolver()).Solve(prob))

// print solutions
(*
let file = System.IO.File.CreateText(filename + ".out")
for solution in solutions do
file.Write(solution + "\n")
file.Close()
*)

let mutable chars = 0
for sol in solutions do
chars <- chars + sol.Length
Console.WriteLine("chars returned: " + chars.ToString());

//just to keep the console running
let secs = (DateTime.Now - time).Seconds
Console.WriteLine("took us approx. " + secs.ToString() + " secs.");
Console.ReadKey() |> ignore

4. Folgend3, F# Solver

// contains the solver for the polygon problem


namespace Solver

module Seq =
let pmap f l =
seq { for a in l -> async { return f a } }
|> Async.Parallel
|> Async.RunSynchronously

open System

type PolygonSolver() =
static let toI str =
System.Double.Parse((string)str)

static let fst3 (x,_,_) = x
static let snd3 (_,y,_) = y
static let trd3 (_,_,z) = z

static let ang p = Math.Atan2(fst3 p, snd3 p)

static let pointCompare p1 p2 =
let a1 = ang p1
let a2 = ang p2
if a1 < a2 then 1 else
if a1 > a2 then -1 else
0

let mutable sol = ""

member public this.Solve(problem:string) =
sol <- ""
let numbers = problem.Split(' ')
// start with 1 to skip the first, as it is the number of points following
let points = [ for i in 1 .. 2 .. numbers.Length-2 do yield (toI(numbers.GetValue(i)), toI(numbers.GetValue(i+1)), (float)(i-1)/2.0) ]
let midpoint = (points |> List.map fst3 |> List.average, points |> List.map snd3 |> List.average, 0.0)
let output = points
|> List.map (fun p -> (fst3 p - fst3 midpoint, snd3 p - snd3 midpoint, trd3 p))
|> List.sortWith pointCompare
|> List.iter (fun p -> (sol <- sol + (trd3 p).ToString() + " "))
sol.Trim()