No Room for Monsters

View as PDF

Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

Skr needs to start writing his thesis, but being a skilled procrastinator, he has been coming up with various errands. Today, he decided to tidy up his room.

He first perfectly aligned his rectangular wardrobe, rectangular bookshelf, and rectangular desk to the 3 corners of his rectangular room, so that there is no space between the corner of the room and the aforementioned furniture. But, he is facing a challenge with placing his bed in the fourth corner of the room.

The floor bed Skr wants to place in the fourth corner of his room is a convex polygon with \(\mathbf{N}\) vertices. Being afraid of there being monsters underneath the normal beds is what led Skr to purchase a floor bed. Out of the same fear, he now wants to make sure that there is as little space as possible between the floor bed and the corner of the room.

Unfortunately, Skr had a panic attack while thinking of how he could achieve this with his unusual bed. While he’s making himself some green tea to relax, could you help him find the area of the minimum space that could be left between the bed and the corner of the room if the bed is placed optimally?


The first line of input contains the integer \(\mathbf{N}\), denoting the number of vertices of the bed.

Each of the following \(\mathbf{N}\) lines contain 2 numbers, \(\mathbf{X_i}\) and \(\mathbf{Y_i}\) denoting the coordinates of one of the vertices of the bed. The polygon vertices given in the input are listed in clockwise or counterclockwise order.

  • \(3 \leq \mathbf{N} \leq 4 \cdot 10^4\)
  • \(-10^9 \leq \mathbf{X_i}, \mathbf{Y_i} \leq 10^9\)


The output should consist of a single line containing a number indicating the minimum area that can be left between the bed and the corner of the room.


  • In order for the output to be considered as correct, its absolute or relative error from the correct answer should not exceed \(10^{-6}\).
  • You may assume that Skr’s room is big enough to accommodate this weird bed.


Input 1:

0 0
5 0
5 4
0 4

Output 1:


Input 2:

6.868348 10
2.571865 8.639367
0.742547 5.231152
0.0 3.171880
0.984830 0.0
4.034411 0.566237
7.368639 3.338222
10.0 7.564563

Output 2: