VertHorizInter | Topcoder Archive

Problem Statement

You will be given a list of line segments in the plane. A line from point (x1,y1) to (x2,y2) will be denoted by the String (quotes for clarity): "x1 y1 x2 y2". Each line given will be vertical or horizontal. No two lines will intersect at more than a single point. You will return a String[] containing the intersection points. Each element of the returned list will represent a single point. Each point returned should be formatted as (quotes for clarity) "x y" where x and y are the x and y coordinates of the point, respectively. x and y must be separated by a single space. All integers in this problem (input or returned) should have no extra leading zeros. The returned points should be sorted in increasing order by x-coordinate. If two points have the same x-coordinate, sort by increasing y-coordinate.

Definition

Class:: VertHorizInter
Method:: howMany
Parameters:: String[]
Returns:: String[]
Method signature:: String[] howMany(String[] lines)
(be sure your method is public)

Constraints

lines will contain between 2 and 50 elements inclusive.
Each element of lines will contain between 7 and 19 characters inclusive.
Each element of lines will be formatted as "x1_y1_x2_y2" where'_' denotes a single space.x1,y1,x2, and y2 denote integers with no extra leading zeros between 0 and 1000 inclusive.
Each element of lines will contain no leading or trailing whitespace.
No element of lines will be a single point (the endpoints for a given line will be distinct).
Each element of lines will be either a horizontal or vertical line.
The intersection of any two elements of lines will be at most a single point.

Examples

```
{"0 0 10 0",
 "5 0 5 10",
 "0 5 10 5"}
```
```
Returns: { "5 0",  "5 5" }
```
Looks something like | | ---------|--------- | | ---------|--------- So there are 2 intersection points. Since they have the same x-coordinate, sort them by y-coordinate.
```
{"0 5 10 5",
 "10 5 20 5"}
```
```
Returns: { "10 5" }
```
Two horizontal lines that share an endpoint. One intersection point.

{"0 0 0 1",
 "0 1 1 1",
 "1 1 1 0",
 "1 0 0 0"}

Returns: { "0 0",  "0 1",  "1 0",  "1 1" }

A little box.

{"0 0 0 5","1 0 1 5","2 0 2 5","3 0 3 5",
 "0 0 5 0","0 1 5 1","0 2 5 2","0 3 5 3"}

Returns: { "0 0",  "0 1",  "0 2",  "0 3",  "1 0",  "1 1",  "1 2",  "1 3",  "2 0",  "2 1",  "2 2",  "2 3",  "3 0",  "3 1",  "3 2",  "3 3" }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.