# 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);                         set.add(new Point(0, 42));         set.add(new Point(666, 42));         System.out.println("size=" + set.size());     } }```
This may or may not be your problem. Hard to say without knowing what your problem is.