01204212/nearby search

From 01204212-59

You are given a locations of players, monsters, and the radius. Output the total number of monsters seen by any players.

Input format:

• First line: n m r (where n is the number of players, m is the number of monsters, and r is a radius)
• The next n lines, for each line the co-ordinate for each player: x y
• The next m lines, for each line the co-ordinate for each monster: x y

Test data: Download here

A few answers:

• n100: 5
• n1000: 311
• n5000: 7803
• n10000: 31072

Some code

GameObject

public class GameObject {

	private double x;
	private double y;

	GameObject(double x, double y) {
		this.setX(x);
		this.setY(y);
	}

	public double distanceTo(GameObject o) {
		return Math.sqrt((getX() - o.getX()) * (getX() - o.getX()) +
				(getY() - o.getY()) * (getY() - o.getY()));
	}
	
	public double getX() {
		return x;
	}

	public void setX(double x) {
		this.x = x;
	}

	public double getY() {
		return y;
	}

	public void setY(double y) {
		this.y = y;
	}
}

Player

public class Player extends GameObject {

	Player(double x, double y) {
		super(x, y);
	}
}

Monster

public class Monster extends GameObject {

	Monster(double x, double y) {
		super(x, y);
	}

}