BdOI 2013 National Problem 6

Discuss everything related to IOI here. For more general or advanced topics use CS forum.

Moderators:Labib, bristy1588

User avatar
bristy1588
Posts:92
Joined:Sun Jun 19, 2011 10:31 am
BdOI 2013 National Problem 6

Unread post by bristy1588 » Wed Jan 15, 2014 12:20 pm

In the country of Giftland, everything is considered as 2D. Little Gugua has $ N $ friends. She
wants to send gifts to all of her friends. All of her gift items can be considered as $2D$ filled
circles of various radii. Gugua went to PackNsend Courier Service to send all of her gifts.
PackNsend company offers $2D$ flexible boxes (you can consider those as flexible envelops) of
various sized square shapes. Each gift requires one box. The gifts must be put in those
square shaped envelops and then the square has to be adjusted to fit the gift in it tightly.
Figure2.JPG
See the Figure for Explanation
Figure2.JPG (16.69KiB)Viewed 7138 times
That is, turn a square to a rhombus so that the circle touches all the sides. Length of the sides of the adjusted rhombus should be (obviously!) equal to the initial
square. The company also charges 1unit/area of the enclosed adjusted envelop. Gugua collected $ N $ envelops of various sizes from the company. As Gugua is very little, all of her gifts were also very little. So she found that any of her gifts can be placed in any of those envelops, and then those envelops can be
adjusted to fit the gifts. Gugua has to pay for the total area of all the adjusted rhombuses.
Your job is to help Gugua to find the minimum area that is required to pack all her gifts using
the square envelops and then adjusting them to rhombuses.

INPUT
First line specifies the test case number $ T (T <= 100) $. Then $T $ test cases follow, each case
starts with an integer,$ N (1 <= N <= 100) $, denoting the number of gifts/envelops. Then two
lines follow. The first line contains $N $integers, $G_i (1 <= i <= N) $, each denoting the radius of $i^{th}$
gift. Next line contains N integers, $S_j$, each denoting the length of side of $j^{th}$ square shaped envelops. No value will be greater than 1000. You can safely assume that, $ S_i >= 2*G_j$ (for all $1 <= i,j <= N$).

OUTPUT
For each line, print the case number, starting from 1, and then print the minimum total area
of the adjusted envelops as described above.

SAMPLE INPUT

Code: Select all

2
4 
1 1 1 1
2 2 2 2
4
1 2 3 4
8 9 10 11
SAMPLE OUTPUT

Code: Select all

Case 1: 16
Case 2: 180
Bristy Sikder

Post Reply