404639: GYM101597 B Triangle in a Triangle

This year's public viewing of SWERC will take place on the famous Triangular Plaza, which is delimited by three perfectly straight roads. Due to weather concerns you have been hired to design a rain cover for the event. This cover should of course be triangular (as is tradition for the Triangular Plaza) and cover as much of the Plaza as possible. The only other restriction is that the rain cover's corners must be fixed on 3 of the lampposts that are standing along the roads. Can you figure out the maximal area of the Plaza you can cover?

The first three lines of input contain pairs of integers, the x- and y-coordinates of the 3 corners A, B, C of the Plaza. It is guaranteed that 0 ≤ x, y ≤ 10⁶. The next line contains a single integer n ≥ 1, the number of lampposts on the line segment . The following line contains n integers d_i in ascending order, where d_i is the distance between the corner A and the i-th lamppost. The next two lines are of the same format but for the line segment and the corner B. The last two lines are of the same format but for the line segment and the corner C. It is guaranteed that the lampposts are on the segment between two corners. A lamppost may however be in a corner. In total there will be less than 10⁶ lampposts. (In case you are worried about precision: it is also guaranteed that all triangles of lampposts that have an area of at least 70% of the solution will have angles that are all > 20 degrees).

Print a single floating point number, the maximal area of the Plaza that can be covered. The answer is considered correct if it is within a 10^- 6 absolute or relative error margin.

0 0
6 0
6 7
2
1 5
2
2 6
1
5

12.0000000