It was a tough year for Per. After finishing his post-doc and going to a lot of interviews, he finally got a job at a university on the other side of the country and had just 2 weeks to find a new apartment. In the end he managed to find one – a really old and dusty apartment. He spent the whole weekend cleaning, throwing away old stuff and repainting the walls. On Sunday evening after 12 hours of work, he couldn’t take it anymore. He just rested on the floor, covered in paint and dust.
The room he just painted was empty, only a lamp was mounted to the ceiling. As he switched it on, he noticed that the light rays coming from the lamp formed a cone and covered some parts of the floor and walls. All the work exhausted his body, so he couldn’t move, but his mind was still working and wanted to solve some hard problems. He started wondering about the area covered by the light from the lamp.
Problem specification
The room has a horizontal floor, a horizontal ceiling, and vertical walls. The floor is a convex polygon. (In the easy data set the polygon is an axes-parallel rectangle.) There is a lamp mounted somewhere on the ceiling of the room. The lamp emits a cone of light downwards. The axis of the cone is vertical.
You are given the height of the room, the description of the floor, the location of the lamp and the angle at the apex of the cone of light emitted by the lamp.
Your goal is to calculate the total area of all lit surfaces in the room. (One of these surfaces will always be on the floor. There may be additional lit surfaces on some of the walls.)
Input specification
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of a series of lines. The first line contains space separated floating point numbers lx, ly, h, and α. The first two numbers are the horizontal coordinates of the lamp. The third number is the height of the room (and at the same time the vertical coordinate of the lamp). The last number is the angle at which the lamp emits light. (For any ray of light from the lamp, the angle between the ray and the axis of the cone is at most α∕2.)
The second line of a test case contains the number n of vertices of the floor. Each of the next n lines contains 2 floating point numbers xi,yi – the coordinates of the i-th vertex of the floor. The coordinates are given in counterclockwise order. The z-coordinate of the floor is 0.
In the easy data set in each test case we have n = 4 and the polygon is an axes-parallel rectangle.
In the hard data set in each test case we have n ≤ 100 and the polygon is convex.
Output specification
For each test case output one line with one floating point number – the total area of all surfaces that are directly reached by the light of the lamp. Output at least six decimal places. Solutions with a relative or absolute error at most 10−6 will be accepted.
Example
