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.

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
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
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
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
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 http://www.spoj.com/BSCPROG/error/10534416
I cant understand
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.