Connection Status:
Competition Arena > PolylineUnion

PolylineUnion

SRM 368 · 2007-10-02 · by misof

SRM 368 · 2007-10-02 · by misof · Brute Force, Geometry
Class Name: PolylineUnion
Return Type: int
Method Name: countComponents
Arg Types: (vector<string>)
Problem Statement

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.

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.

7)
{"10,10-20,10 20,10-15,18 15,18-10,10"}
Returns: 1

A triangle.

Submissions are judged against all 125 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PolylineUnion with a public method int countComponents(vector<string> polylines) · 125 test cases · 2 s / 256 MB per case

Submitting as anonymous