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.

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 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.

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 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.

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:2012-09-09
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

hide comments
2021-05-28 03:26:53
actually we have to account for the spaces between input testcases
(python 3).
2020-03-21 09:30:46
http://discuss.spoj.com/t/what-does-100-means-when-i-submitted-my-mst-code-it-showed-100-instead-if-ac/26356/2
2019-11-11 10:22:53
I am sure that my code works. But getting no points. How sad for me! Anyone to give me any advice?
2019-05-16 08:44:59
can some one please explain this problem to me i am not able to understand it what we have to do
2019-04-01 10:58:41
after many error compilations i got 100pts LOL
2018-06-26 15:18:54
how do i take the input for p, c, l;
i'm first using scanf to take the input as p or c or l and then using switch statement for the follow up values.
but im stuck as i'm using my own version;
how to take object type and the co-ordinates input in a same line using c.
2018-01-18 17:45:41
Every time i get different score: 20, 40, 60. Something is wrong with tests because i tested my code with mixed objects and seems correct.

Last edit: 2018-01-18 17:46:19
2017-11-06 15:24:52 BartĀ³omiej W
Maximum number of points for this problem is 100 - tests are divided into 5 categories, as is stated in problem description, but for each category you get 20, not 2, points, so e.g. if you get 40 points then program successfully ran through first two categories, but has problem calculating MBR for lines.
Don't know if the number of points is an error in problem description or is it poorly worded - you get 2 points for each test, but there are 10 test in category, so for each category you get 20 points.
2017-09-17 07:39:05
I have 20 points and I don't know why. In all my examples it looks okay... Just walking on.

=(Francky)=> Check
4
1
p 3 3
1
p -3 3
1
p 3 -3
1
p -3 -3

It could be useful.
=(ano302)=>
3 3 3 3
-3 3 -3 3
3 -3 3 -3
-3 -3 -3 -3
Totally fine. I assume there is something with the 5 different test cases.
Are they given all at once?
is the program started 5 times?
or is the programm started once but with 5 different parts, so giving the number of test cases 5 times during the input?

=(Francky)=> Then check
4
l 3 3 -3 -3
(and 3 other diags)
=(ano302)=>
look here: https://pastebin.com/tS4ELCZd
everything looks fine

Last edit: 2017-09-19 11:41:51
2017-07-25 18:53:30
i got 40. what is the maximum points ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.