TopCoder problem "FaceFinder" used in TCCC '03 Semifinals 1 (Division I Level Two)



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).
 

Definition

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

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.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1657

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4491&pm=1657

Writer:

brett1479

Testers:

lbackstrom , schveiguy

Problem categories:

Geometry