# Interesting CS problem. Need help.

• 05-01-2009, 11:54 PM
xtrmi
Interesting CS problem. Need help.
I am working on implementing the plane sweep algorithm to solve the closest points problem and it works, but about 10/1000 times I get the wrong answer. The instructions I'm following say to have an array of x coordinates sorted and use a TreeSet to sort the points inside the strip by their y coordinates. I'm getting errors when I try to add two points to the BST and they have the same Y coordinate. I've been hitting my head on the wall for a while now. Does anybody have any suggestions or hints?
• 05-02-2009, 03:51 AM
pbrockway2
Perhaps you could post some brief code to illustrate the problem?

When I first used TreeSet I was bitten by the requirement stated in the API documentation that "the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface."

Suppose I had a TreeSet made from a comparator that just compared two points' y-coords and return zero if the y-coords were equal. What would happen when I added two distimct points with the same y-coord to the set?

Code:

import java.awt.Point;
import java.util.Comparator;
import java.util.SortedSet;
import java.util.TreeSet;

public class TreeSetEg {

static Comparator<Point> yCoordComp = new Comparator<Point>() {
public int compare(Point o1, Point o2) {
return o1.y - o2.y;
}
};

public static void main(String[] args) {
SortedSet<Point> set = new TreeSet<Point>(yCoordComp);