Morning Morning


2019-07-17 18:40 AKDT

Morning Morning


2019-07-17 21:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -744 days 9:09:42

Time elapsed


Time remaining


Problem C
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.


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.


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}$.


  • $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