# Thread: Interesting CS problem. Need help.

1. Member
Join Date
Jan 2009
Posts
9
Rep Power
0

## 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?

2. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,716
Rep Power
18
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?

Java 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);

System.out.println("size=" + set.size());
}
}```
This may or may not be your problem. Hard to say without knowing what your problem is.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•