Carol picks a vertex of a convex cake and Carla picks a diagonal from it to split the cake, then Carol keeps the larger piece under optimal play from both.
Medium7GeometryGame theoryTwo pointersNo attempts yetTime limit3sMemory limit256 MBCarol and Carla are roommates. They threw a big party yesterday, and today they want to divide the cake that is left over. People were careless when cutting themselves a slice, so the cake is now a prism whose top and bottom faces are the same simple convex polygon.
To make the division more fun, the two agreed on the following game. Carol first picks a vertex v of the top face. Carla then picks another vertex w that is not adjacent to v, where adjacent means joined directly by one edge of the polygon. They cut the cake by extending the segment vw downwards, which gives two separate pieces, each one a prism. Finally Carol takes the piece she prefers and Carla gets the other one.
Carla saw at once that this rule favors Carol. Work out exactly how large that advantage is.
The cake has height 2, so the volume of a piece is twice the area of its top face. Both of them choose so that the volume of the piece they end up with is as large as possible. Compute the volume each of them gets.
The first line contains the number of vertices N of the polygonal top face. (4≤N≤105)
Each of the next N lines contains two integers X and Y, the coordinates of one vertex. (−108≤X,Y≤108)
The vertices are given in counter clockwise order and form a simple convex polygon. No three points in the input are collinear.
Print one line with two integers, the volume of the piece Carol gets and the volume of the piece Carla gets, in that order, when both choose optimally. Both values are always integers.