### Question:
LineSegmentIntersection { public static List<Point> solve(List<LineSegment> input) { List<Point> result = new ArrayList<>(); List<Event> events = buildEvents(input); events.sort((a, b) -> { int compare = Integer.compare(a.xPos, b.xPos); if (compare == 0) { return Integer.compare(a.type, b.type); } return compare; }); RangeSearchBST<Integer, Event> bst = new RangeSearchBST<>(); for (Event event : events) { if (event.type == X_IN) { bst.put(event.ySmall, event); } else if (event.type == X_OUT) { bst.remove(event.ySmall); } else { for (int y : bst.search(event.ySmall, event.yLarge)) { result.add(new Point(event.xPos, y)); } } } return result; }  static List<Point> solve(List<LineSegment> input);  }### Answer:
@Test public void noIntersectionTest() { LineSegment lineSegment1 = new LineSegment(new Point(0, 0), new Point(0, 1)); LineSegment lineSegment2 = new LineSegment(new Point(1, 2), new Point(-1, 2)); List<Point> res = LineSegmentIntersection.solve(Arrays.asList(lineSegment1, lineSegment2)); assertEquals(0, res.size()); }
@Test public void intersectionTest() { LineSegment lineSegment1 = new LineSegment(new Point(0, 0), new Point(0, 2)); LineSegment lineSegment2 = new LineSegment(new Point(1, 1), new Point(-1, 1)); List<Point> res = LineSegmentIntersection.solve(Arrays.asList(lineSegment1, lineSegment2)); assertEquals(1, res.size()); assertEquals(new Point(0, 1), res.get(0)); }
@Test public void intersectionEdgeLimitTest() { LineSegment lineSegment1 = new LineSegment(new Point(0, 0), new Point(0, 1)); LineSegment lineSegment2 = new LineSegment(new Point(1, 1), new Point(-1, 1)); List<Point> res = LineSegmentIntersection.solve(Arrays.asList(lineSegment1, lineSegment2)); assertEquals(1, res.size()); assertEquals(new Point(0, 1), res.get(0)); }
@Test public void randomTest() { int upLimit = 100; for (int i = 0; i < 100; i++) { if (i % 20 == 19) upLimit <<= 1; Set<LineSegment> xLines = generateLine(upLimit / 5, upLimit, true); Set<LineSegment> yLines = generateLine(upLimit / 20, upLimit, false); List<LineSegment> testInput = new ArrayList<>(); testInput.addAll(xLines); testInput.addAll(yLines); List<Point> res = LineSegmentIntersection.solve(testInput); assertEquals(expect(xLines, yLines), new HashSet(res)); } }