1. Java, Gunaar Hage

/**
* FWP-Fach: ACM programming Contest WS 08/09 "534 - Frogger"
* Verdict: Accepted / run Time: 0.330
*
* Gunnar Hage, gunnarhage@gmx.de
* AP5(IFB5A) Nov. 2008
*
* Problembeschreibung: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=475
* Ich löse das Problem indem ich den Minimalen Spannbaum aufbaue, bis beide Steine im Spannbaum enthalten sind.
* Die entfernung der zuletzt verbundenen Steine entspricht dann dem minimax.
Input:
2
0 0
3 4

3
17 4
19 4
18 5

0
Output:
Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414

*/

import java.io.IOException;
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
import java.util.Locale;
import java.util.StringTokenizer;


public class Main {

public static void main(String[] args) {
double adja[][];
double stonesX[];
double stonesY[];
int scenario = 0;
int stoneNumber = 0;
StringTokenizer st = null;
while(st == null || st.countTokens() == 0)
st = ReadAll();
// Bis nurnoch die "0" im Tokenizer enthalten ist.
while(st.countTokens()> 1){
scenario++;
//Nur vor dem ersten Scenario keine Leerzeile drucken.
stoneNumber = Integer.parseInt(st.nextToken());
adja = new double[stoneNumber][stoneNumber];
stonesX = new double[stoneNumber];
stonesY = new double[stoneNumber];
// Einlesen der Steincoordinaten.
for(int i=0;i<stoneNumber;i++){
stonesX[i] = Integer.parseInt(st.nextToken());
stonesY[i] = Integer.parseInt(st.nextToken());
}
// Berechnug der Adjazenzmatrix. Für alle Werte rechts der Dieagonalen (Der Graph ist vollständig und ungerichtet)
for(int i=0;i<stoneNumber;i++){
double x1 = stonesX[i];
double y1 = stonesY[i];
for(int f=0;f<i;f++){
if(i==f)
adja[i][f] = Double.MAX_VALUE;
else{
double x2 = stonesX[f];
double y2 = stonesY[f];
adja[i][f] = Math.sqrt((x1-x2)*(x1-x2) + ((y1-y2)*(y1-y2))); // Berechnung der entfernung zueinander.
}
}
}
// Adjazenzmatrix fertig befüllt. Algorithmus ausführen. minimax suchen.
double frogDistance = calculateFrogDistance(adja);

//Frogdistance kann ich in prinf nicht einfach ausgeben, weil er für double ein "," stat einem "." beneutzt
DecimalFormat df = new DecimalFormat("0.000",new DecimalFormatSymbols(Locale.ENGLISH));
System.out.printf("Scenario #" + scenario + "\nFrog Distance = " + df.format(frogDistance) + "\n\n");
}
System.exit(0);
}
//Der eigentliche Algorithmus
static double calculateFrogDistance(double[][] adja){
double frogDistance = 0;
int[] stoneNames = new int[adja.length];
//Steine benennen
for(int i=0;i<stoneNames.length;i++)
stoneNames[i] = i;

int minI = 0; int minF = 0; double min = Double.MAX_VALUE;
// Solange Freddys (0) und Fionas(1) Stein nicht im Minimalen Spannbaum sind.
while(stoneNames[0] != stoneNames[1]){
//Minimum in der Matrix finden.
min = Double.MAX_VALUE;
for(int i=0;i<adja.length;i++){
for(int f=0;f<i;f++){
if(adja[i][f] < min){
min = adja[i][f];
minF = f;
minI = i;
}
}
}
//dieses Minimum muss der Frosch mind. springen.
frogDistance = min;
//Den Weg in der Matrix unbrauchbar machen.
adja[minI][minF] = Double.MAX_VALUE;
//Alle Steine die an Stein minF hängen umbenennen in den namen den der Stein minI hat.
int overwrite = stoneNames[minF];
for(int i=0;i<stoneNames.length;i++)
if(stoneNames[i] == overwrite)
stoneNames[i] = stoneNames[minI];
}
//Freddys und Fionas Stein haben nun den gleichen namen und sind im Minimalen Spannbaum enthalten.
return frogDistance;
}

//Veränderte ReadLine... liest jetzt alles von der eingabe und gibt einen StringTokenizer zurück.
static StringTokenizer ReadAll()
{
byte lin[] = new byte [10000];
int lg = 0, car = -1;
try
{
while (System.in.available()>0)
{
car = System.in.read();
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
//if (car < 0) return (null); // eof
new String();
return (new StringTokenizer(new String (lin, 0, lg)));
}
}


2. C, Doina Logofatu


/**
* ACM programming Contest WS 08/09
* UVa Status: Accepted
* Run Time: 0.250
* Programming Language: C
* @author Doina Logofatu logofatu@hm.edu
*/

#include <stdio.h>
#include <math.h>
#include <memory.h>

long min(long a, long b){
if(a>b) return b;
return a;
}

long max(long a, long b) {
if(a>b) return a;
return b;
}

int main() {
long a[202][202];
int x[202], y[202];
int s=1;
int n, i, j, k;

while(scanf("%d",&n) && n) {

for(i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);

for(i=0;i<n;i++)
for(j=i;j<n;j++)
a[i][j]=a[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);

for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j] = min(max(a[i][k],a[k][j]), a[i][j]);

printf("Scenario #%d\n", s++);
printf("Frog Distance = %.3lf\n\n",sqrt((double)a[0][1]));

}
return 0;
}

3. Zweite Version: C, Doina Logofatu

Einzige Veränderung: Mit MACROS für MIN und MAX

/**
* ACM programming Contest WS 08/09
* UVa Status: Accepted
* Run Time: 0.090
* Programming Language: C
* @author Doina Logofatu logofatu@hm.edu
*/

#include <stdio.h>
#include <math.h>
#include <memory.h>

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

int main() {
long a[202][202];
int x[202], y[202];
int s=1;
int n, i, j, k;

while(scanf("%d",&n) && n) {

for(i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);

for(i=0;i<n;i++)
for(j=i;j<n;j++)
a[i][j]=a[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);

for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j] = MIN(MAX(a[i][k],a[k][j]), a[i][j]);

printf("Scenario #%d\n", s++);
printf("Frog Distance = %.3lf\n\n",sqrt((double)a[0][1]));

}
return 0;
}


4. C, Doina Logofatu

Veränderung zu 2.: Array mit doubles statt ints

/**
* ACM programming Contest WS 08/09
* UVa Status: Accepted
* Run Time: 0.170
* Programming Language: C
* @author Doina Logofatu logofatu@hm.edu
*/

#include <stdio.h>
#include <math.h>
#include <memory.h>

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

int main() {
double a[202][202];
int x[202], y[202];
int v=1;
int n, i, j, k;

while(scanf("%d",&n) && n) {

for(i=0;i<n;i++)
scanf("%d%d",&x[i],&y[i]);

for(i=0;i<n;i++)
for(j=i;j<n;j++)
a[i][j]=a[j][i]=sqrt((double)((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));

for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j] = MIN(MAX(a[i][k],a[k][j]), a[i][j]);

printf("Scenario #%d\n", v++);
printf("Frog Distance = %.3lf\n\n", a[0][1]);

}
return 0;
}


5. C++, Doina Logofatu

/**
* ACM programming Contest WS 08/09
* UVa Status: Accepted
* Run Time: 0.240
* Programming Language: C++
* @author Doina Logofatu logofatu@hm.edu
*/

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

using namespace std;

struct pos{
int x;
int y;
};

// the distance between two points
double dist( pos a, pos b ) {
int abs, ord;
abs = b.x - a.x;
ord = b.y - a.y;
return sqrt( (double)(ord*ord + abs*abs) );
}

int main() {
int n;
int scenario = 0;
pos stone[200];
double d[200][200];
double fdistance;

cin >> n;

while( n != 0 ) {


scenario++;

for( int i = 0; i < n; i++ )
cin >> stone[i].x >> stone[i].y;

for( int i = 0; i < n; i++ )
for( int j = 0; j < n; j++ )
d[i][j] = dist( stone[i], stone[j] );

for( int k = 0; k < n; k++ )
for( int i = 0; i < n; i++ )
for( int j = 0; j < n; j++ )
d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));

fdistance = d[0][1];

cout << "Scenario #" << scenario << endl;
cout << setiosflags(ios::fixed) << setprecision(3)
<< "Frog Distance = " << fdistance << endl;
cout << endl;
cin >> n;
}

return 0;
}

6. Doina Logofatu, C++

/**
* ACM programming Contest WS 08/09
* UVa Status: Accepted
* Run Time: 0.270
* Programming Language: C++
* @author Doina Logofatu logofatu@hm.edu
*/

#include <iostream>
#include <math.h>
#include <iomanip>
#include <algorithm>

const size_t MaxNumStones = 200;
typedef std::pair<int,int> pos;

/** the distance between two points */
inline double distantza(const pos &a, const pos &b ) {
return hypot(b.first - a.first,b.second - a.second);
}

int main(int numargs,char * args[]) {

int scenario = 0;
size_t n;
std::cin >> n;

pos stone[MaxNumStones];
double d[MaxNumStones][MaxNumStones];
double fdistance;


while( n > 0 && n<=MaxNumStones ) {
scenario++;
for( size_t i = 0; i < n; i++ )
std::cin >> stone[i].first >> stone[i].second;

for( size_t i = 0; i < n; i++ )
for( size_t j = 0; j < n; j++ )
d[i][j] = distantza( stone[i], stone[j] );

for( size_t k = 0; k < n; k++ )
for( size_t i = 0; i < n; i++ )
for( size_t j = 0; j < n; j++ )
d[i][j] = std::min( d[i][j], std::max( d[i][k], d[k][j] ) );

fdistance = d[0][1];

std::cout << "Scenario #" << scenario << std::endl;
std::cout << setiosflags(std::ios::fixed) << std::setprecision(3)
<< "Frog Distance = " << fdistance << std::endl;
std::cout << std::endl;
std::cin >> n;
}

return 0;
}

7. JAVA

/**
* ACM programming Contest WS 08/09
* UVa Status: Accepted
* Run Time: 0.860
* Programming Language: Java
* @author Doina Logofatu logofatu@hm.edu
*/


import java.text.*;
import java.util.*;

public class Main {

    private static final class Pos {
        int x;
        int y;
       
        private Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
        double distance(Pos other) {
            return Math.hypot(this.x-other.x, this.y-other.y);
        }
    }
       
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int scenario = 0;
        DecimalFormat df = new DecimalFormat("0.000",new DecimalFormatSymbols(Locale.ENGLISH));
        while(true) {
            int n  = sc.nextInt();
            if(n<=0) {
                break;
            }
            Pos[] stones = new Pos[n];           
            for (int i = 0;i<n;i++) {
                stones[i] =  new Pos(sc.nextInt(),sc.nextInt());
            }
           
            double d[][] = new double[n][n];
           
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    d[i][j] = stones[i].distance(stones[j]);

            for (int k = 0; k < n; k++)
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                        d[i][j] = Math.min(d[i][j], Math.max(d[i][k], d[k][j]));

            System.out.print("Scenario #");
            System.out.println(++scenario);
            System.out.print("Frog Distance = ");
            System.out.println(df.format(d[0][1]));
        System.out.println();
           
        }     
    }
}