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.
Input
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
Output two spacedelimited numbers with 3 digits after decimal points  area values for the pessimist and optimist correspondingly.
Sample test(s)
Input
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
Output
8.000 16.000
Author:  Michael R. Mirzayanov

Resource:  ACM ICPC 20042005, NEERC, Southern Subregional Contest

Date:  Saratov, October 7, 2004

Server time: 20180222 09:57:35  Online Contester Team © 2002  2016. All rights reserved. 

