267. Optimist vs. Pessimist

time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard

An optimist and a pessimist decided to have a small party. They ordered K rectangular pies in the confectionery. It is known that K <= 10. They got a list of N pies to select K desired. But they decided to ask to deliver any K under the condition that their summary area is maximum possible. There are two candles on each pie. The candles are so thin, that they can be treated as points. As the optimist and pessimist permanently argue, they want to slice each pie with linear cut into two pieces of equal size. Each piece should contain one candle. The cut can not pass through a candle. If they can not do so, they don't eat it, and leave this pie for later use. The optimist wants to know what summary area he will get in the best case, while the pessimist wants to know the area in the worst case.

The first line of the input file contains two integer numbers N and K (1 <= N <= 1000; 0 <= K <= min(N, 10)). The following N lines contain the description of N pies. Each pie is defined by 12 numbers -- pairs of 4 corner coordinates and coordinates of two candles. Each pie is delivired on its own baking tray, so the coordinates of each pie are given correspondingly to the centre of its tray. Candles can be located on the edge of the pie. All coordinates are integers, less then 10^3 by absolute value. All pies have a positive area.

Output two space-delimited numbers with 3 digits after decimal points -- area values for the pessimist and optimist correspondingly.

Sample test(s)

3 2
0 0 0 4 4 0 4 4 1 1 3 1
0 0 0 4 4 0 4 4 2 3 2 4
0 0 0 4 4 0 4 4 1 3 3 3

8.000 16.000

Author:Michael R. Mirzayanov
Resource:ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:Saratov, October 7, 2004

Server time: 2017-09-25 22:45:17Online Contester Team © 2002 - 2016. All rights reserved.