|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 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.
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)
|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|
2019-07-10 13:40:20 kuszi
Yes, the rectangle is axis aligned.
That Minimum Bounding Rectangle is oriented horizontally I assume? Build with only vertial and horizontal edges.
I am getting green result but time and memory as 0 sec and 0 K respectively.
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
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 http://www.spoj.com/BSCPROG/error/14837845
2015-04-08 09:21:27 kamran siddique
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 http://www.spoj.com/BSCPROG/error/10534416
I cant understand