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
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 5.7hard
Statistics Show
Source IDI Open 2018
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in