1.

/**
* Angewandte Mathematik, SS11
* Problem: 11966 - Galactic Bonding
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3117
* @author Fabian, Trampusch
* @author Robert Schwarz
* @version 1.0, 28.06.2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.540
*/

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

public class Main {
public static void main(String[] args) throws NumberFormatException,
IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
StringTokenizer st;
int numberOfStars;
double distanceOfConstellations;
star[] starArray;
int numberOfConstellations;
boolean emptyArray = false;
int numberOfCases = Integer.parseInt(br.readLine());

for (int i = 1; i <= numberOfCases; i++) {
st = new StringTokenizer(br.readLine());
numberOfStars = Integer.parseInt(st.nextToken());
distanceOfConstellations = Double.parseDouble(st.nextToken());
starArray = readStars(numberOfStars, br);
numberOfConstellations = 0;
emptyArray = false;

for (int k = 0; (k < numberOfStars) && !emptyArray; k++) {
if (starArray[k] != null) {
numberOfConstellations++;
star currentStar = new star(starArray[k].getX(),
starArray[k].getY());
starArray[k] = null;
starArray = search(starArray, numberOfStars, distanceOfConstellations,
currentStar);
emptyArray = true;
for (int t = 0; t < numberOfStars; t++) {
if (starArray[t] != null)
emptyArray = false;
}
}
}

System.out.println("Case " + i + ": " + numberOfConstellations);
}
}

public static star[] search(star[] starArr, int numberOfStars,
double distanceOfConst, star s) {

for (int j = 0; j < numberOfStars; j++) {
if (starArr[j] != null) {
double a = s.getX() - starArr[j].getX();
double b = s.getY() - starArr[j].getY();
double distance = Math.sqrt((a * a) + (b * b));
if (distance < distanceOfConst && distance != 0) {
star currentStar = new star(starArr[j].getX(),
starArr[j].getY());
starArr[j] = null;
starArr = search(starArr, numberOfStars, distanceOfConst,
currentStar);
}
}
}
return starArr;
}

public static class star {
private double posX, posY;

star(double x, double y) {
posX = x;
posY = y;
}

double getX() {
return this.posX;
}

double getY() {
return this.posY;
}
}

public static star[] readStars(int numberOfStars, BufferedReader br)
throws IOException {
StringTokenizer st;
star[] starArr = new star[numberOfStars];

for (int i = 0; i < numberOfStars; i++) {
st = new StringTokenizer(br.readLine());
starArr[i] = new star(Double.parseDouble(st.nextToken()),
Double.parseDouble(st.nextToken()));
}

return starArr;
}
}



2.
/*
Author: Patrick Bédat
Problem: 11966 Galactic Bonding
Method: BFS
Time: 1.3
Date: 27.06.2011
*/
import java.awt.Point;
import java.awt.geom.Point2D;
import java.util.*;
import java.io.*;

public class Main
{

public static void main(String[] args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;

int tc = Integer.parseInt(reader.readLine());

for (int testCase = 1; testCase <= tc; testCase++)
{
Star.nextid = 0;
Double[][] distCache = new Double[1000][1000];
st = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(st.nextToken());
double D = Double.parseDouble(st.nextToken());

Set<Star> stars = new HashSet<Star>();
for (int i = 0; i < N; i++)
{
st = new StringTokenizer(reader.readLine());
double x = Double.parseDouble(st.nextToken());
double y = Double.parseDouble(st.nextToken());
Star s = new Star(x, y);
stars.add(s);
}

int nConstellations = 0;

Set<Star> crossedOut = new HashSet<Star>();

while (!stars.isEmpty())
{
Stack<Star> queue = new Stack<Star>();
Iterator<Star> it = stars.iterator();
queue.push(it.next());
it.remove();
crossedOut.add(queue.peek());

nConstellations++;

while (!queue.isEmpty())
{
Star current = queue.pop();

for (Star star : stars)
{
Double d = distCache[current.id][star.id];
if(d == null)
{
d = star.distance(current);
distCache[star.id][current.id] = d;
distCache[current.id][star.id] = d;
}

if (d < D && !crossedOut.contains(star))
{
queue.push(star);
crossedOut.add(star);
}
}

for (Star star : crossedOut)
stars.remove(star);
}
}

System.out.printf("Case %d: %d%n", testCase, nConstellations);
}
}
}

class Star extends Point2D
{

double x;
double y;
public static int nextid;
public int id;

public Star(double x, double y)
{
this.setLocation(x, y);
id = nextid++;
}

@Override
public double getX()
{
return x;
}

@Override
public double getY()
{
return y;
}

@Override
public void setLocation(double x, double y)
{
this.x = x;
this.y = y;
}

@Override
public int hashCode()
{
return id;
}

@Override
public boolean equals(Object obj)
{
return hashCode() == ((Star) obj).hashCode();
}
}