No tags yet

No tag edit access

The problem statement has recently been changed. View the changes.

×
time limit per test: 0.25 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: 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.

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

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 2004-2005, NEERC, Southern Subregional Contest |

Date: | Saratov, October 7, 2004 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/24/2021 18:03:23 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|