Cutting Land
Time limit2sMemory limit128 MB
Given a convex quadrilateral, find the cut between two vertices or side-midpoints that splits it into two polygons with the most balanced areas.
- Level
Medium4 of 10
- Topics
- Geometry, Brute force, Implementation
- Solved
- No attempts yet
Problem
A plot of land has the shape of a convex quadrilateral. You want to cut it with one line segment so that it is divided into two polygons whose areas are as close as possible.
Each endpoint of the cutting segment must be one of the quadrilateral's vertices or one of the midpoints of its four sides. The segment must actually divide the land into two polygons; a segment lying along one side does not count.
Among all valid cuts, find the two areas obtained when the difference between them is minimized.
Input
The first line contains the coordinates of the four vertices of the quadrilateral in order, either clockwise or counterclockwise: x1 y1 x2 y2 x3 y3 x4 y4.
Each coordinate is an integer whose absolute value is at most 10000.
The given quadrilateral is convex, and every interior angle is less than 180 degrees.
Output
Print the two areas on one line, with the smaller area first. An absolute or relative error of at most 10^-3 is accepted.