Submit  All submissions  Best solutions  Back to list 
HS12MBR  Minimum Bounding Rectangle 
Compute the Minimum Bounding Rectangle (MBR) that surrounds the given set of 2D objects, i.e., the axisaligned rectangle, which contains all of the specified objects and is the one with minimum area among all rectangles with this property.
Input
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 x_{1} y_{1} x_{2} y_{2}, where x_{i}, y_{i} are the coordinates of the endpoints of the line.
Successive test cases are separated by an empty line.
Output
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 xcoordinate of the lower left corner, then the ycoordinate of the lower left corner, the xcoordinate of the upper right corner and the ycoordinate 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.
Example
Input: 3 1 p 3 3 2 c 10 10 20 c 20 20 10 1 l 0 0 100 20 Output: 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 
Date:  20120909 
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:  20130824 14:33:14 
hide comments


20190710 13:40:20 kuszi
Yes, the rectangle is axis aligned. 

20190626 17:11:26
That Minimum Bounding Rectangle is oriented horizontally I assume? Build with only vertial and horizontal edges. 

20170525 14:03:03
I am getting green result but time and memory as 0 sec and 0 K respectively. Help needed 

20150920 11:55:01
Hi, I am getting an error " 0 (limit : 2) " Clicking on 0 opens this page :http://www.spoj.com/error/15167401 which is not helpful. Please help 

20150808 09:13:11 kuszi
@Pikachu NZEC for every test case (+smarty does not work here  to be fixed soon) 

20150806 23:08:36 Pikachu
Can anyone explain this error http://www.spoj.com/BSCPROG/error/14837845 

20150408 09:21:27 kamran siddique
AC :) 

20140719 19:39:47 kamran siddique
I'm also getting "0(limit:2)" ... i can't understand! 

20131215 16:16:33 kuszi
@Subham Das Wrong answer (formating is broken  sorry for the inconvenience) 

20131215 15:28:54 dabanggboy
it gives me this error http://www.spoj.com/BSCPROG/error/10534416 I cant understand 