Public submissions
Source code of every submission to this problem in this contest will be visible for everyone since 2013-08-24 14:33:14.

HS12MBR - Minimum Bounding Rectangle

Compute the Minimum Bounding Rectangle (MBR) that surrounds the given set of 2D objects, i.e., the axis-aligned rectangle, which contains all of the specified objects and is the one with minimum area among all rectangles with this property.


First, you are given t (t<100) - the number of test cases.

Each of the test cases starts with one integer n (n < 100) - the number of objects in the set. In the successive n lines, the descriptions of the objects follow.

Each object is described by one character and some parameters:

  • a point: p x y, where x and y are point coordinates.
  • a circle: c x y r, where x and y are the center coordinates and r is the radius of the circle.
  • a line segment: l x1 y1 x2 y2, where xi, yi are the coordinates of the endpoints of the line.

Successive test cases are separated by an empty line.


For each of the test cases output four numbers - the coordinates of the two points that correspond to the lower left and the upper right corner of the MBR, in the following order: first the x-coordinate of the lower left corner, then the y-coordinate of the lower left corner, the x-coordinate of the upper right corner and the y-coordinate of upper right corner.

You can assume that all object parameters are integers and that -1000 -1000 1000 1000 is a bounding rectangle for all of them.


p 3 3 

c 10 10 20
c 20 20 10

l 0 0 100 20

3 3 3 3 
-10 -10 30 30
0 0 100 20

Test case description

test 1: points only    (2 pts)
test 2: circles only   (2 pts) 
test 3: lines only     (2 pts)
test 4: mixed          (2 pts)
test 5: mixed          (2 pts)

Added by:kuszi
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS PY_NBC
Resource:High School Programming League
Public source code since: 2013-08-24 14:33:14

hide comments
2019-07-10 13:40:20 kuszi
Yes, the rectangle is axis aligned.
2019-06-26 17:11:26
That Minimum Bounding Rectangle is oriented horizontally I assume? Build with only vertial and horizontal edges.
2017-05-25 14:03:03
I am getting green result but time and memory as 0 sec and 0 K respectively.
Help needed
2015-09-20 11:55:01
I am getting an error " 0 (limit : 2) "
Clicking on 0 opens this page :
which is not helpful. Please help
2015-08-08 09:13:11 kuszi
@Pikachu NZEC for every test case (+smarty does not work here - to be fixed soon)
2015-08-06 23:08:36 Pikachu
Can anyone explain this error
2015-04-08 09:21:27 kamran siddique
AC :)
2014-07-19 19:39:47 kamran siddique
I'm also getting "0(limit:2)" ... i can't understand!
2013-12-15 16:16:33 kuszi
@Subham Das Wrong answer (formating is broken - sorry for the inconvenience)
2013-12-15 15:28:54 dabanggboy
it gives me this error
I cant understand
© All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.