Connection Status:
Competition Arena > PolylineAreas

PolylineAreas

TCO18 Parallel Round 4 · 2018-04-20 · by misof

TCO18 Parallel Round 4 · 2018-04-20 · by misof · Geometry, Graph Theory, Search
Class Name: PolylineAreas
Return Type: long[]
Method Name: findAreas
Arg Types: (string)
Problem Statement

Problem Statement

This problem has a non-standard time limit: 4 seconds.

You are given the String polyline: the description of a polyline in the plane. Each segment of the polyline is parallel to one of the coordinate axes. This polyline divides the plane into some finite connected regions. Your task is simple: find the area of each such region.

To keep the input small (and constructing challenges easier), the polyline is given as a simple program for a robot that moves and draws the polyline along its path. The program has the following syntax: 

program ::= "" | command | command+program
command ::= instruction | cycle
instruction ::= "F" | "L" | "R" | "["+program+"]"
cycle ::= number+instruction

Additional specifications:

  • The instructions "F", "L", and "R" mean "move 1 unit forward", "turn 90 degrees left", and "turn 90 degrees right", respectively.
  • A cycle means that the given instruction should be executed the given number of times in a row; "number" must be a positive integer between 2 and 10^6, inclusive.

Let A be the sequence of the areas of all finite regions of the plane, sorted in non-decreasing order. If A has at most 200 elements, return A. Otherwise, return the first 100 elements of A followed by the last 100 elements of A.

Notes

  • The polyline may cross and overlap itself arbitrarily.
  • The output must always be sorted in non-decreasing order.

Constraints

  • polyline will be a valid program.
  • polyline will contain between 1 and 2000 characters, inclusive.
  • When executing the program in polyline the robot will make at most 250,000 moves and/or turns.
Examples
0)
"FRFLF"
Returns: { }

A squiggly line. This line forms no finite regions in the plane, the entire infinite plane is still connected.

1)
"4[100FR]"
Returns: {10000 }

This line is the boundary of a 100x100 square.

2)
"2[2[100FR]]"
Returns: {10000 }

The same square. Note that cycles may be nested.

3)
"47[100FR]"
Returns: {10000 }

Still the same square (but now the robot goes around its boundary multiple times).

4)
"1000000[]"
Returns: { }

A valid empty program with a long cycle that does nothing.

5)
"4[6FR]FR6FL2FL6FR3FRFR6FL2FL6F"
Returns: {1, 2, 2, 3, 3, 4, 6, 6, 9 }

A more complicated polyline that draws a 6x6 square subdivided into nine regions of various sizes.

6)
"4[6FR]FR6FL2FL6FR3FRFR6FL2FL4F"
Returns: {1, 2, 2, 3, 3, 4, 6, 15 }

The same polyline, only the last segment is shorter. Thus, there are now only eight finite regions instead of nine.

7)
"3FRFRFLFLFRFR3FRFRFLFLFRF"
Returns: {7 }

A closed path around a region shaped like the letter H.

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

Coding Area

Language: C++17 · define a public class PolylineAreas with a public method vector<long long> findAreas(string polyline) · 116 test cases · 2 s / 256 MB per case

Submitting as anonymous