FaceFinder
TCCC '03 Semifinals 1 · 2003-04-04 · by brett1479
TCCC '03 Semifinals 1 · 2003-04-04 · by brett1479 · Geometry
Problem Statement
Problem Statement
You will be given a list of line segments in an infinite x-y plane. Your method should return how many separate regions there are in the plane once the segments are added. Two points are in the same region if there exists a path from one point to the other that doesn't cross a line segment. The line segments will be given in a String[] lines. Each element of lines will be a single space delimited list of 4 integers. The elements will be formatted as (quotes for clarity) "x0 y0 x1 y1" denoting a line segment from (x0,y0) to (x1,y1). Note that there will always be exactly 1 infinite region that is not completely enclosed by the given line segments. In addition, to make things easier, the line segments will only be horizontal, vertical or diagonal (a diagonal line segment is one whose slope is 1 or -1).
Notes
- Although the line segment endpoints are bounded by input constraints, when calculating regions, consider the plane to be infinite.
Constraints
- lines will contain between 1 and 50 elements, inclusive.
- Each element of lines will contain between 7 and 15 characters, inclusive.
- Each element of lines will be formatted as "N N N N" where each N represents an integer between 0 and 100 inclusive with no extra leading zeros, and each N is separated by a single space.
- No line segment will have 0 length.
- Each line segment will be horizontal, vertical, or diagonal.
- No two elements of lines will represent the same line segment. This includes cases where one segment goes from point A to point B, and another goes from B to A.
Examples
0)
{"0 0 100 100","0 100 100 0"}
Returns: 1
A large X.
1)
{"10 10 20 10","10 10 10 20","20 20 10 20","20 20 20 10"}
Returns: 2
A single box.
2)
{"0 0 0 10","1 0 1 10","2 0 2 10","3 0 3 10","4 0 4 10",
"5 0 5 10","6 0 6 10","7 0 7 10","8 0 8 10","9 0 9 10",
"10 0 10 10","0 0 10 0","0 1 10 1","0 2 10 2","0 3 10 3",
"0 4 10 4","0 5 10 5","0 6 10 6","0 7 10 7","0 8 10 8",
"0 9 10 9","0 10 10 10"}
Returns: 101
A 10x10 checkerboard.
3)
{"0 0 0 1","0 0 0 2","0 0 0 3","0 0 0 4","0 0 0 5",
"0 0 1 0","0 0 2 0","0 0 3 0","0 0 4 0","0 0 5 0",
"5 0 0 5","4 0 0 4","3 0 0 3","2 0 0 2","1 0 0 1"}
Returns: 6
A weird drawing.
4)
{"0 0 0 1", "0 0 1 0", "0 0 1 1", "1 0 1 1", "0 1 1 1", "1 0 0 1"}
Returns: 5
This is a 1x1 box with both diagonals filled in.
Submissions are judged against all 36 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FaceFinder with a public method int howMany(vector<string> lines) · 36 test cases · 2 s / 256 MB per case