VPL1_BA - Spring Iceblocks

Last winter has passed and Dickie is out in the field, he needs to cross the lake but Spring has melted much of it. The lake is now just a pile of ice blocks floating everywhere. Dickie needs an ice block large enough to use as a raft. Dickie asks your help to find the biggest piece.

Dickie has the coordinates of the points defining each ice block, he enumerated each block and he can remember where each one is individually, so you just have to tell him which one is the biggest one, but this piece must be large enough for him, so you must check the block is at least 30000.00cm2. If you don't find one big enough you must tell him or else he will die trying to cross (and you don't want it to happen right?)

Input

Each input file starts with one integer T denoting the number of test cases. Each teast case start with a single integer N denoting the number of ice blocks in the lake followed by the description of each block like follows: an integer P denoting the number of points and then P lines with each point in the form Xi Yi defining the polygon that describes the ice block.

NOTE: Each block is defined as a sequence of consecutive points of a convex closed polygon. As a help, you can find the center of this polygon and calculate each sub-triangle's area to find the total area of the polygon by adding each subtriangle.

Output

For each test case you must print a line containing the case number and the index of the ice block with the biggest surface that also is bigger than 30000.00cm2. In the case you can't find a block large enough you must print "There is not a block large enough."

Example

Input:
2
2
5
6357.49 -7105.07
6343.05 -7061.56
6261.56 -7056.95
6242.61 -7106.15
6301.81 -7157.69
4
-1000.0 -1000.0
1000.0 -1000.0
1000.0 1000.0
-1000.0 1000.0
1
3
-1.0 0.0
1.0 0.0
0.0 1.0

Output:
Scenario #1: 2
Scenario #2: There is not a block large enough.

Constraints

Subtask 1 (40%):

  • 1 <= T <= 50
  • 0 <= N <= 50
  • 3 = P
  • -10000.0 <= Xi, Yi <= 10000.0

Subtask 2 (60%):

  • 1 <= T <= 100
  • 0 <= N <= 1000
  • 3 <= P <= 50
  • -10000.0 <= Xi, Yi <= 10000.0

Added by:Venezuelan Programming League
Date:2013-03-08
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2023-02-28 20:33:12 Simes
I see no one has got a score over 90. Is there something wrong with test case 7?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.