1. 

package contestVolumes.volume110;

import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 11096 - Nails
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=22&page=show_problem&problem=2037
*
* @author Siegfried Ippisch
* @version 1.0
*
* Method : convex hull
* Status : Accepted
* Runtime: 0.332
*/
public class Nails {

public static final double EPSILON = 0.000000000001;

public static class Point implements Comparable<Point>{
public final double x,y;
public double angel=0, distance=0;

public Point(double x, double y){
this.x = x; this.y = y;
}

public double setDistance(Point other){
double diffX = this.x - other.x;
double diffY = this.y - other.y;
this.distance = Math.sqrt(diffX*diffX+diffY*diffY);
return this.distance;
}

public double setAngle(Point other){
this.angel = Math.atan( (this.y - other.y) / (this.x - other.x) );
return this.angel;
}

public int compareTo(Point other) {
if(this.angel < other.angel-EPSILON) return -1;
if(this.angel > other.angel+EPSILON) return 1;
if(this.distance < other.distance-EPSILON) return -1;
if(this.distance > other.distance+EPSILON) return 1;
return 0;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
long temp;
temp = Double.doubleToLongBits(x);
result = prime * result + (int) (temp ^ (temp >>> 32));
temp = Double.doubleToLongBits(y);
result = prime * result + (int) (temp ^ (temp >>> 32));
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point other = (Point) obj;
if (Double.doubleToLongBits(x) != Double.doubleToLongBits(other.x))
return false;
if (Double.doubleToLongBits(y) != Double.doubleToLongBits(other.y))
return false;
return true;
}

public String toString(){
return "("+x+"|"+y+")";
}
}

public static class Polygon{
public LinkedList<Point> points;

public Polygon(LinkedList<Point> points){
this.points = points;
}

public Polygon convexHull(){

// remove equal points
HashSet<Point> filter = new HashSet<Point>(this.points);
LinkedList<Point> points = new LinkedList<Point>(filter);

// get p0
Point p0 = points.get(0);
for(Point p: points)
if(p.x < p0.x || p.x == p0.x && p.y < p0.y)
p0 = p;

// set angel and distance relative to p0
for(Point p: points){
p.setAngle(p0);
p.setDistance(p0);
}

// sort Points by angle, and distance
Collections.sort(points);

// remove same angel points
for(int i=1; i<points.size();)
if(points.get(i-1).angel == points.get(i).angel)
points.remove(i-1);
else i++;

if(points.size() <= 3)
return new Polygon(points);

points.remove(p0);

// initial new list
LinkedList<Point> list = new LinkedList<Point>();
list.add(p0);
list.add(points.remove(0));
list.add(points.remove(0));

// Graham scan
while(!points.isEmpty()){
Point n = points.remove(0); // new Point
while(true){
Point m = list.getLast(); // middle
Point l = list.get(list.size()-2); // last
if((n.x-m.x)*(l.y-m.y) - (n.y-m.y)*(l.x-m.x) <= 0)
list.removeLast();
else break;
}
list.add(n);
}

return new Polygon(list);
}

public double length(){
if(this.points.size() < 2)
return 0;

double length = this.points.get(0).setDistance(this.points.get(this.points.size()-1));
for(int i=1; i<this.points.size(); i++)
length += this.points.get(i-1).setDistance(this.points.get(i));
return length;
}

public String toString(){
return this.points.toString();
}
}

public static void main(String[] args){
Scanner in = new Scanner(System.in);
int t = in.nextInt();

while(t-- > 0){
int rLength = in.nextInt();
int n = in.nextInt();

// load points for polygon
LinkedList<Point> points = new LinkedList<Point>();
while(n-- > 0)
points.add(new Point(in.nextDouble(),in.nextDouble()));
Polygon polygon = new Polygon(points);

// length of convex hull
polygon = polygon.convexHull();
double nLength = polygon.length();

System.out.printf("%.5f\n",Math.max(rLength, nLength));
}

in.close();
}

}


2.

package acm_11096_nails;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_11096_nails
* Link:
*
* @author Martin Lambeck
* @version 1.0, 31.08.2010
*
* Method : graham scan
* Status : Accepted
* Runtime: 0.272
*/


public class Main
{
static Scanner sc = new Scanner(System.in);

public static void main(String... args)
{
int cases = sc.nextInt();

for (int i = 0; i < cases; i++)
testcase();
}

public static void testcase()
{
double initial = sc.nextInt();
int n = sc.nextInt();

Point[] pts = new Point[n];

for (int i = 0; i < n; i++)
pts[i] = new Point(sc.nextInt(), sc.nextInt());


//only 1 nail
if (n <= 1)
{
System.out.printf("%.5f%n", initial);
//sc.nextLine();
return;
}

Point p0 = pts[0];

//find point with lowest y (and lowest x among them on tie)
for (Point p : pts)
if ((p.y < p0.y) || ((p.y == p0.y) && (p.x < p0.x)))
p0 = p;

//set angle between p0,x-axis,p for any Point p
for (Point p : pts)
if (p != null)
p.setAngle(p0);

p0.angle = -1;

Arrays.sort(pts); //sort by angle, ascending



LinkedList<Point> stack = new LinkedList<Point>();


stack.addLast(pts[0]); //push first two points on stack
stack.addLast(pts[1]);


for (int i = 2; i < n; i++)
{
while (!pts[i].isLeft(stack.get(stack.size()-2), stack.get(stack.size()-1)))
stack.removeLast();

stack.addLast(pts[i]);
}


double dist = 0.0;
Point prev = stack.getLast();
Point p;

while (stack.size() > 0)
{
p = stack.pop();
dist += dist(prev, p);
prev = p;
}


System.out.printf("%.5f%n", Math.max(dist, initial));


//sc.nextLine();
}



static double dist(Point p, Point q)
{
double dx = p.x - q.x;
double dy = p.y - q.y;

return Math.hypot(dx, dy);
}
}

class Point implements Comparable<Point>
{
long x;
long y;
double angle;
double dist;

public Point(int xx, int yy)
{
x = xx;
y = yy;
}

public void setAngle(Point p)
{
double dx = x - p.x;
double dy = y - p.y;

if (dy < 0)
throw new IllegalStateException();
else if ((dx == 0.0) && (dy == 0.0))
angle = 0;
else if (dx == 0.0)
angle = Math.PI / 2;
else if (dx < 0)
angle = Math.atan(Math.abs(dx) / dy) + Math.PI / 2;
else
angle = Math.atan(dy / dx);

angle = angle / Math.PI * 180;
dist = Main.dist(this, p);
}

public int compareTo(Point p)
{
if (angle < p.angle)
return -1;

if (angle > p.angle)
return 1;

if (dist < p.dist)
return -1;

if (dist > p.dist)
return 1;

return 0;
}

public boolean isLeft(Point p0, Point p1)
{
return ((p1.x - p0.x) * (y - p0.y) - (x - p0.x) * (p1.y - p0.y)) >= 0;
}
}