TopCoder problem "PolylineUnion" used in SRM 368 (Division I Level Two)



Problem Statement

    

A polyline is a sequence of line segments such that each segment starts at the point where the previous segment ended.

If two polylines have a common point, we say that they belong to the same picture. The common point does not have to be an endpoint of a line segment.

Your method will be given a String[] polylines. Concatenate the elements of polylines to get a space-separated list of polyline descriptions. Each polyline description consists of one or more point descriptions, separated by single dashes ('-'). Each point is described by its two non-negative integer coordinates, separated by a comma (',').

Return the number of pictures in the union of all the given polylines.

 

Definition

    
Class:PolylineUnion
Method:countComponents
Parameters:String[]
Returns:int
Method signature:int countComponents(String[] polylines)
(be sure your method is public)
    
 

Notes

-The point sequence that defines a polyline may contain the same point more than once, and even consecutive points are allowed to be equal.
-A polyline may be just a single point.
 

Constraints

-polylines will have the format described in the problem statement.
-polylines will contain between 1 and 50 elements, inclusive.
-Each of the elements in polylines will contain between 0 and 50 characters, inclusive.
-Each coordinate of each point specified in polylines will be between 0 and 10000, inclusive.
-The point coordinates in polylines will not contain unnecessary leading zeros.
 

Examples

0)
    
{"0,0-10,10 0,10-10,0"}
Returns: 1

Two intersecting line segments form a single picture.

1)
    
{"0,0-10,5 5,0-15,5-10,10-5,5"}
Returns: 2

Two non-intersecting polylines.

2)
    
{"1","3,0-5,5 4,0-4,20"}
Returns: 2
Note that you first have to concatenate the elements of polylines and only then parse the resulting string.
3)
    
{"10,0-10,1-9,2-9,3-8,4 ","8,2-9,2-10,3 ","12,2-11,2-9,1"}
Returns: 1

Together, these three polylines form a single picture. From a graph theoretical point of view, this picture can be seen as a tree with 11 vertices. (Ten of them are the given points and one is the intersection of 10,1-9,2 and 11,2-9,1.)

4)
    
{"0,0-10,0-0,0 20,0-8,0-20,0"}
Returns: 1
The union of these two polylines is the line segment 0,0-20,0.
5)
    
{"1,1 2,2 3,3 4,4 3,3-4,4"}
Returns: 3
A single point is a special case of a polyline.
6)
    
{"10,10-20,10 20,10-15,18 15,18-10,10"}
Returns: 1
A triangle.
7)
    
{"1,1 1,1"}
Returns: 1

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10936&pm=8249

Writer:

misof

Testers:

PabloGilberto , vorthys , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Geometry