1.

/* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #534 (Frogger)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=475
*
* @author Dennis Wilfert
* @author Johann Studt
* @version 1.0, 06/16/2009
*
* Status : Accepted
* Runtime: 0.228
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.DecimalFormat;
import java.util.StringTokenizer;

public class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer token;
StringBuilder output = new StringBuilder();
// Zahlen auf drei Stellen nach dem Komma runden runden
DecimalFormat df = new DecimalFormat();
df.applyPattern( "#,###,##0.000" );

// 2-Dimensionales Array zum berechnen der verschiedenen Abstände
int[][] distances;
// Koordinaten der Steine
int[][] coordinates;
// Zähler für die Scenarios
int counter=0;
// Anzahl der Koordinaten
int n;

int max;

while(true){
// Anzahl der Koordinaten
n = Integer.parseInt(reader.readLine());
// Beenden wenn n == 0
if(n==0)break;

// 2-Dimensionales Array zum berechnen der verschiedenen Abstände
distances = new int[n][n];
// Koordinaten der Steine
coordinates = new int[n][2];

// Zahlen einlesen
for(int i=0;i<n;i++){
token = new StringTokenizer(reader.readLine());
coordinates[i][0] = Integer.parseInt(token.nextToken());
coordinates[i][1] = Integer.parseInt(token.nextToken());
}

// Algorithmus von Floyd und Warshall

for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
// Für jede x/y-Kombination den Abstand berechnen ( (x(i)-x(j))²+(y(i)-y(j)² ) ohne die Wurzel zu ziehen
// Wuzel wird nur am Ende für den kürzesten Abstand gezogen
distances[i][j]=(coordinates[i][0]-coordinates[j][0])*(coordinates[i][0]-coordinates[j][0])+(coordinates[i][1]-coordinates[j][1])*(coordinates[i][1]-coordinates[j][1]);

for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
// Den kürzesten Wege suchen
if(distances[i][k]>distances[k][j])
max=distances[i][k];
else
max=distances[k][j];

if(max<distances[i][j])
distances[i][j]=max;
}

counter++;
// Ausgabe erstellen
output.append("Scenario #");
output.append(counter);
output.append("\nFrog Distance = ");
// Abstand durch Ziehen der Wuzel berechnen und formatiert ausgeben
output.append(df.format(Math.sqrt(distances[0][1])));
output.append("\n\n");

// Leerzeile in der Eingabe überspringen
reader.readLine();
}
System.out.print(output);

}

}

2.


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem: Frogger (534)
* @author Christian Mitterreiter
* @author Rolf Luigs
* @version 1.0, 07/03/2009
* Status : Accepted
* Runtime: 0.524
*/


import java.util.Scanner;


public class Main {


public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int count = 1;

while(n > 0) {

double [][] in = new double[1000][1000];
int[] x = new int[300];
int[] y = new int[300];


for(int i=0;i<n;i++) { //einlesen der Werte
x[i] = sc.nextInt();
y[i] = sc.nextInt();
}

for(int i=0;i<n;i++) { //distance berechnen
for(int j=i;j<n;j++) {
in[i][j]=in[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
}

for(int k = 0; k<n;k++) {
for(int i = 0; i<n; i++) {
for(int j = 0; j<n; j++) {
in[i][j] = Math.min(in[i][j], Math.max(in[i][k], in[k][j])); //min-max-distance
}
}
}

System.out.printf("Scenario #%d\n", count++);
System.out.printf("Frog Distance = %.3f\n", Math.sqrt(in[0][1])); //Ausgabe

n = sc.nextInt();
System.out.printf("\n");
}
}
}

3.

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #534 Frogger
* Link: http://uva.onlinejudge.org/external/5/534.pdf
*
* @author Schirm , Mathauser , Mohr

* @version 1.0, 07/05/09
*
* Status : Accepted
* Runtime: 0.256
*/

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int testcase = 1;
int countStones;

while (true) {
countStones = sc.nextInt();

if (countStones == 0)
break;

int[][] stone = new int[countStones][2];
double[][] dist = new double[countStones][countStones];

for (int i = 0; i < countStones; i++) {
stone[i][0] = sc.nextInt();
stone[i][1] = sc.nextInt();
}

// Startort ist Zielort
if (stone[0][0] == stone[1][0] && stone[0][1] == stone[1][1]) {
System.out.println("Scenario #" + testcase);
System.out.printf("Frog Distance = %.3f%n", 0.000);
System.out.println();
}

else {
// Distanz zwischen den Steinen im dist-Array speichern
for (int i = 0; i < countStones; i++)
for (int j = 0; j < countStones; j++)
if (i != j) {
if (dist[j][i] == 0)
dist[i][j] = Math.hypot(stone[i][0]
- stone[j][0], stone[i][1]
- stone[j][1]);
else
dist[i][j] = dist[j][i];
}

boolean changed = true;

// Schleife laufenlassen bis keine Änderungen mehr auftreten
while (changed) {
changed = false;

// Schleife über alle Kombinationen von Steinen
for (int i = 0; i < countStones; i++)
for (int j = 0; j < countStones; j++) {
if (i != j) {

// Maximum der beiden Strecken 0-i und i-j
double max = dist[0][i] > dist[i][j] ? dist[0][i]
: dist[i][j];

// max muss kleiner sein als die Distanz vom
// Startstein zum Stein i, dann der Distanz
// 0-j den Wert max zuweisen
if (max < dist[0][j]) {
dist[0][j] = max;
dist[j][0] = max;
changed = true;
}
}
}
}

// Ausgabe
System.out.println("Scenario #" + testcase);
System.out.printf("Frog Distance = %.3f%n", dist[0][1]);
System.out.println();
}
testcase++;
}
}
}


4.

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem 534 - Frogger
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=475
*
* @author Miesel Christoph
* @author Seilbeck Robert
* @author Wolfram Andre
* @version X.0, 07/06/2009
*
* Status : Accepted
* Runtime: 0.488
*/

import java.util.*;

public class Frogger
{
private static int scenario = 0;

private static double[][] area;

private static Map<Integer, ArrayList<Integer>> coord = new HashMap<Integer,ArrayList<Integer>>();

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

int n = 0;
int x1, x2, y1, y2;
double distance = 0f;

while((n = sc.nextInt()) != 0)
{

scenario++;
coord.clear();
area = new double[n][n];


for(int i = 0; i < n; i++)
{
ArrayList<Integer> oneStone = new ArrayList<Integer>();
oneStone.add(sc.nextInt());
oneStone.add(sc.nextInt());
coord.put(i, oneStone);
}


for(int i = 0; i < coord.size(); i++)
{
for(int m = 1; m < coord.size(); m++)
{
x2 = coord.get(m).get(0);
y2 = coord.get(m).get(1);
x1 = coord.get(i).get(0);
y1 = coord.get(i).get(1);

distance = Math.hypot((double)(~(x2-x1)+1), (double)(~(y2-y1)+1));
area[i][m] = distance;
}
}


for(int h = 0; h < n; h++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
area[i][j] = Math.min(Math.max(area[i][h], area[h][j]), area[i][j]);
}

System.out.println("Scenario #"+scenario);
//System.out.print(String.format("Frog Distance = %.3f\n",area[0][1]).replace(",","."));
System.out.printf("Frog Distance = %.3f\n\n",area[0][1]);


}
}
}

5.


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #11233 (Frogger)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=7&problem=475&mosmsg=Submission+received+with+ID+7232867
*
* @author Christian Posselt
* @author Jonathan Schubert
* @version 1.0, 07/06/2009
*
* Status : Accepted
* Runtime: 0.268
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


class Main
{
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int stoneAmount,scenario = 1;
StringBuilder builder = new StringBuilder();
//read all the test cases
for(stoneAmount = Integer.parseInt(reader.readLine()); stoneAmount != 0; scenario ++, stoneAmount = Integer.parseInt(reader.readLine()))
{
if(stoneAmount == 0) // end of input
continue;
String[] stones = new String[stoneAmount];
//read all the stone cordinates
for(int index = 0;index < stoneAmount;index ++)
stones[index] = reader.readLine();

reader.readLine(); //Skip empty line

int[][] a = new int[stoneAmount][stoneAmount]; //stone distances

//Build adjacency matrix for all stones
for(int outerIndex = 0; outerIndex < stoneAmount; outerIndex++)
{
for(int innerIndex = 0; innerIndex < stoneAmount; innerIndex++)
{
int[]cord1 = cords(stones[outerIndex]);
int[]cord2 = cords(stones[innerIndex]);
int di = dist(cord1[0],cord1[1],cord2[0],cord2[1]);
if(di == 0)
di = Integer.MAX_VALUE;
a[outerIndex][innerIndex] = di;
}
}

//toString(a);
builder.append("Scenario #"+scenario+"\n");
builder.append("Frog Distance = ");
builder.append(String.format("%01.3f\n\n",Math.sqrt(floydWarshall(a))));

//toString(a);
}
builder.deleteCharAt(builder.length()-1);
System.out.println(builder.toString());


}

//floyd warshall algorithm see wikipedia for more info:
//http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
static int floydWarshall(int[][] adj)
{
int n = adj.length;
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
adj[i][j] = min(max(adj[i][k],adj[k][j]),adj[i][j]);

return adj[1][0];
}

static int min(int x , int y)
{
if(x < y)
return x;
return y;
}

static int max(int x , int y)
{
if(x > y)
return x;
return y;
}

static void toString(int[][]a)
{
for(int[] b: a)
{
for(int c: b)
System.out.print(c+" ");
System.out.println();
}
}


static int dist(int x1, int y1, int x2, int y2)
{
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

static int[] cords(String s)
{
StringTokenizer n = new StringTokenizer(s);
int[] result = new int[2];
result[0] = Integer.parseInt(n.nextToken());
result[1] = Integer.parseInt(n.nextToken());
return result;
}
}

6.

/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #534 Frogger
* Link: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1103
*
* @author Fabian Seidl
* @author Marcel Sachse
* @version 1.0, 6/07/2009
*
* Status : Accepted
* Runtime: 0.252
*/

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

public class Main
{
private static PrintWriter out = new PrintWriter(System.out);
private static Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException
{
int counter = 0;
int numOfStones;

while((numOfStones = scanner.nextInt()) != 0) // Input ends with 0
{
counter++;

/** Entfernungsmatrix */
int[][] d = new int[numOfStones][numOfStones];

/** Koordinatenmatrix
* xy[0] sind Freddies Koordinaten
* xy[1] sind Fionas Koordinaten
* */
int[][] xy = new int[numOfStones][2];

// read Stones
for(int i=0;i<numOfStones;i++)
{
xy[i][0] = scanner.nextInt();
xy[i][1] = scanner.nextInt();
}

// direkte Entfernungen (quadrat) berechnen
for(int i=0;i < d.length; i++)
for(int j=0;j < d.length; j++)
{
int dX = xy[i][0]-xy[j][0];
int dY = xy[i][1]-xy[j][1];
d[i][j] = dX*dX + dY*dY; // um Zeit zu sparen zunächst nur Quadrate speichern
}

findMiniMax(d);

// Wurzel ziehen
double frogDist = Math.sqrt(d[0][1]); // d[0][1] steht für die Freddy-Fiona MiniMax Distanz

// Output
out.println("Scenario #"+counter);
out.printf("Frog Distance = %1.3f\n", frogDist);
out.println();
out.flush();
}
}

/**
* MiniMax Algorithmus angelehnt an Floy-Warshall.
* @param d Entfernungsmatrix
*/
private static void findMiniMax(int[][] d)
{
for(int k = 0; k < d.length; k++)
for(int i=0;i < d.length; i++)
for(int j=0;j < d.length; j++)
{
// d[i][j] ist MiniMax der Route von i zu j
// Alternative Route: i -> k und k -> j

// Max der alternativen route i -> k und k -> j
int alt = d[i][k] > d[k][j] ? d[i][k] : d[k][j];

// Prüfe ob alternative Route niedrigeres Max hat -> MiniMax
if(alt < d[i][j]) d[i][j] = alt; // wenn ja wird alternative Kapazität gespeichert
}
}
}

7.

/**
* ACM
* UVa Status: accepted
* Run Time: 0.220
* Category: Floyd-Warschall
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

#define MAX_NODES 200
#define X 0
#define Y 1

#define DELTA_X(a,b) abs(node[a][X] - node[b][X])
#define DELTA_Y(a,b) abs(node[a][Y] - node[b][Y])

#define MIN(a,b) ((a < b)? a : b)
#define MAX(a,b) ((a > b)? a : b)



double m[MAX_NODES][MAX_NODES];
int node[MAX_NODES][2];
int nodes;

double dist(int a, int b)
{
int tmp1 = DELTA_X(a,b);
int tmp2 = DELTA_Y(a,b);
return sqrt(tmp1*tmp1 + tmp2*tmp2);
}

void floydWarshall()
{
for(int k = 0; k < nodes; k++)
for(int i = 0; i < nodes; i++)
for(int j = 0; j < nodes; j++)
m[i][j] = MIN( m[i][j], MAX(m[i][k], m[k][j]) );
}

int main()
{

int caseNumber = 1;
cout << setprecision(3);
cout << showpoint;
cout << fixed;

while(true)
{
cin >> nodes;
if(nodes == 0)
return 0;

// read coordinates
for(int n = 0; n < nodes; n++)
{
cin >> node[n][X];
cin >> node[n][Y];
}

// initialize incidence matrix
for(int i = 0; i < nodes; i++)
for(int j = 0; j < nodes; j++)
m[i][j] = dist(i,j);

floydWarshall();

cout << "Scenario #" << caseNumber++ << endl;
cout << "Frog Distance = " << m[0][1] << endl << endl;
}
}