534-frogger.c

/* 
 * ACM 534: Frogger (ANSI C version)
 * Author: Christopher Vo ([email protected])
 */
#include <stdio.h>
#include <math.h>
#define min(a, b) (((a) < (b)) ? (a) : (b)) 
#define max(a, b) (((a) > (b)) ? (a) : (b)) 
struct point {
  int x, y;
};
double distsq(struct point * a, struct point * b) {
  return (b->x - a->x) * (b->x - a->x) + (b->y - a->y) * (b->y - a->y);
}
int main()
{
  int n;
  int s = 0; 
  int i, j, k;
  while (scanf("%d", &n) > 0) {
    if (n == 0)
      break;

    struct point nodes[n];
    double d[n][n]; 

    for(i = 0; i < n; i++)
      d[i][i] = 0.0;

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

    for (i = 0; i < n; ++i)
      for (j = i + 1; j < n; ++j)
        d[i][j] = d[j][i] = distsq(&nodes[i], &nodes[j]);

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

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

534-frogger.cpp

// ACM 534: Frogger (C++ version)
// Author: Christopher Vo ([email protected])

#include <iostream>
#include <cmath>
#include <cstdio>

struct point 
{
  double x, y;
};

double distsq(const point &a, const point &b)
{
  return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}

int main()
{
  int n; // n: number of nodes
  int s = 0; // s: scenario
  while (std::cin >> n && n != 0) {

    point nodes[n]; // nodes: list of nodes
    double d[n][n]; // d: distance matrix

    // get nodes from input
    for (int i = 0; i < n; ++i) {
      std::cin >> nodes[i].x >> nodes[i].y;
      d[i][i] = 0;
    }

    // get pairwise distances
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        d[i][j] = d[j][i] = distsq(nodes[i], nodes[j]);

    // minimax
    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]));

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

534-frogger.java

// ACM 534: Frogger (Java version)
// Author: Christopher Vo ([email protected])

class Frogger {
  public static void main(String args[]) {
    int n;
    int s = 0;
    java.util.Scanner sc = new java.util.Scanner(System.in);
    while (sc.hasNextInt()) {
      if ((n = sc.nextInt()) == 0)
        break;

      java.awt.Point[] nodes = new java.awt.Point[n];
      double[][] d = new double[n][n];

      // get input
      for (int i = 0; i < n; ++i) 
        nodes[i] = new java.awt.Point(sc.nextInt(), sc.nextInt());
      
      // get distances
      for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
          d[i][j] = d[j][i] = nodes[i].distanceSq(nodes[j]);

      // minimax
      for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
          for (int j = 0; j < n; ++j)
            if ((d[i][k] != 0) && (d[k][j] != 0))
              d[i][j] = Math.min(d[i][j], Math.max(d[i][k], d[k][j]));
      
      // print
      System.out.printf("Scenario #%d\n", ++s);
      System.out.printf("Frog Distance = %.3f\n\n", Math.sqrt(d[0][1]));
    }
  }
}