Problem I
Polygon Game
Jack and Jill are playing a game they call Polygon Game. In this game they start with a convex polygon and then take turns dividing the polygon into smaller parts. They divide the polygon by drawing a straight line from one point on the border of the original polygon to another point on the border of the original polygon. The goal of the game is then to guess which of the resulting polygons has the largest area.
Input
The first line of the input consists of two integers
$N$, $M$: The number of vertices in the
original polygon, and the number of lines drawn by Jack and
Jill.
Then follows $N$ lines,
each consisting of two integers $X_ i$ and $Y_ i$, representing the coordinates
of the $i^\textrm {th}$ of
the vertex in original polygon given in a counter-clockwise
order.
Then follows $M$ lines,
each consisting four real numbers $X_1, Y_1, X_2,$ and $Y_2$, representing the two endpoints
of a line drawn by Jack and Jill.
Output
The output should be a single line consisting of the area of the largest polygon created. Your answer must have an absolute or relative error of at most $10^{-6}$.
Limits
-
$3 \leq N \leq 25$
-
$2 \leq M \leq 50$
-
$M$ will be an even number.
-
$0 \leq X_ i, Y_ i \leq 1\, 000$
-
The polygon’s vertices are distinct.
-
All lines will start and end on the border of the original polygon with an absolute error of at most $10^{-6}$, and all lines will divide the original polygon into two parts.
-
Real numbers in the input will have at most $20$ digits after the decimal point.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 0 0 1 0 1 1 0 1 0 0 1 1 0.5 0 0.5 1 |
0.375 |
