Solution to a Shaping Regions Programming Problem

For the first time in my life while applying for a job decided to proceed with solving qualification tasks (despite some of a reasonable criticism of such practices).

And, as it usually goes with today’s HR-cast, got no reply in a week. Thus, feeling free to spoil it down here.

Shaping Regions

N opaque rectangles (1 <= N <= 1000) of various colors are placed on a white sheet of paper whose size is A wide by B long. The rectangles are put with their sides parallel to the sheet’s borders. All rectangles fall within the borders of the sheet so that different figures of different colors will be seen.

Input

The order of the input lines dictates the order of laying down the rectangles. The first input line is a rectangle "on the bottom".

Line 1: A, B, and N, space separated (1 <= A,B <= 10,000)

Lines 2-N+1: Five integers: llx, lly, urx, ury, color: the lower left coordinates and upper right coordinates of the rectangle whose color is `color’ (1 <= color <= 2500). The color 1 is the same color of white as the sheet upon which the rectangles are placed. The first input line is a rectangle "on the bottom" (below all rectangles) and the last input line is a rectangle "on the top" (not covered with anything).

Output

 

The output file should contain a list of all the colors that can be seen along with the total area of each color that can be seen. The list of colors should be sorted according to color ID. Do not display colors with no area.

  
 

For sample input
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4
Sample output is:
1 91
2 84
3 187
4 38

http://cid-6b8ee681d2c79b18.skydrive.live.com/embedicon.aspx/src/20100314-shaping_regions.linq

Note: It wasn’t explicitly stated what tools/platforms/versions to choose, so I risked to utilise LINQPad queries – they’re basically plain C# code, without VisualStudio.Net-related heavy lifting. (LINQPad can be downloaded freely, as well as a required Microsoft .Net Framework 4.)

About these ads
This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s