In a new wing of the Rijksmuseum in Amsterdam, there is an exhibition of world treasures. The new wing of the museum consists of rectangular rooms. Each room contains exactly one treasure, where each treasure is placed on a square pedestal which is surrounded by glass and wood.
The curator of the Rijksmuseum is intensely worried about treasures being stolen from the new wing of the museum. He decides to place as many distinct security systems as possible in each of the rooms. A security system is composed out of three identical parts, where each part sends an infrared laser beam and has two receivers for detecting the beams sent out by the two other parts. A security system is functional when its parts are placed such that the laser beams form a triangle. In addition, none of the beams forming the triangle is allowed to be obstructed by the pedestal. If there are two security systems in a room that form the same triangle, they are not distinct.
The security system’s parts can only be installed on the pillars that are placed against the walls of the room. There is a pillar placed against the wall of the room per every meter of the wall. Also, a pillar is placed in each corner of the room.
Figure 1: An example of a room with length and width of 1 meter. The pedestal is denoted by the square in the top-right corner of the room. The spots represent the pillars where the security system parts are deployed, while the dashed lines represent the infrared laser beams that are sent out by the security system parts. The pedestal blocks the beam that could be sent from the bottom-left pillar to the top-right pillar and subsequently only 2 of the 4 possible distinct security systems can be placed in this room.
Figure 2: An example of a treasure room with length and width of 2 meters. 13 distinct security systems can be placed in this room.
The curator wishes to know the maximum number of distinct security systems that can be installed in each of the rooms of the museum’s new wing.
For this problem, assume that the pillars are point-like objects, that an infinite number of parts can be placed on a single pillar and that height is no factor for this problem.
Given the length and width of a room plus the width and location of the treasure pedestal, determine the maximum number of security systems that can be installed in the given room.
The input starts with a line containing an integer T, the number of test cases. Then for each test case:
The square pedestal will always fit inside the room and will always be placed such that there is at least a 10−1 meters distance between the pedestal and the walls of the room. It is guaranteed that the distance from each corner of the pedestal to a potential laser beam (i.e. a line between two pillars) is at least 10−4 meters.
For each test case, output one line containing a single integer: the maximum number of security systems that can be installed in the room.
3 1 1 .81 .12 .1 2 2 .6424600 .4334300 0.6500800 2 4 .10 .19 .3
2 13 158