KITEPRBL - Bob and his new kite factory

no tags 

Bob, owner of kite factory decided to make some good money.

He has bought new machine to produce kites, but this machine doesn't have any software in it! He was very sad, oh, so very sad. Every kite is produced from big square sheet of paper.

He didn't want to spend next big sum of money hiring programmers, so he decided to ask you for help.

He wants his machine to:

  • Cut exactly as much color paper as needed to cover kite and then cover it immediately.
  • Make N very little small holes in the kite (through which he can put colorful bows and other shiny things.)
  • At the end he wants his machine to sort convex shape kites and non-convex shapes kites (he thinks that convex shape kites should be transported to "Biedronka" - shop for poor people, so he doesn't want to mix them with really expensive ones.)

Input

In first line there is number T, number of test cases.

In first line of each test case there is number X (X < 200), number of vertices of the each kite.

Then X pairs of number, xi and yi, coordinates of each vertex.

Left-bottom corner of paper have (0, 0) coordinates.

In next line number N (N < 20000), number of holes to make in the kite.

Then N number, xi and yi, coordinates of each hole to make in the kite.

Obviously, hole cannot be made on the perimeter of a kite.

We can assume that no three points are colinear, also there is no point duplicate. Bob always would give you vertices of kite in clockwise order.

Output

For each test case print area (10^-3 precision) of paper which was used to produce each kite, holes which were made successfully, and digit 1 if kite is convex shape, otherwise digit 0. Separate each test case with new line

Example

Input:
1
6
0 0
5 0
4 2
5 4
0 4
1 2
3
1 1
1 2
5 2

Output:
32.000 1 0

Explanation:

32.000 area of paper to cover the kite. Only 1st hole can be made successfully (2nd is on perimeter, 3rd is outside the kite.) Kite has non-convex shape


hide comments
Simes: 2022-09-23 15:35:36

I used asserts to find that the coordinates are all integers between 0 and 1000 (perhaps even smaller.)

It's mighty suspicious that there were 2 ACs in the month the problem was published, and none at all in the eleven years since.

[Rampage] Blue.Mary: 2022-09-23 12:35:26

Agree @Simes. Also the constraints of this problem is unclear according to input section.

Simes: 2022-09-22 15:24:54

The example has the points in anti-clockwise order, not clockwise as stated in the problem.

akababa: 2017-04-17 05:53:13

are they integer points?

aristofanis: 2013-01-08 18:01:52

@author What can we assume for the coordinates of the points? In c++, can they fit in a float?

Lucas Maciel: 2012-08-13 22:17:23

Another test case?


Added by:Krzysztof Lewko
Date:2011-06-09
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64