<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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 space-delimited 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 2004-2005, NEERC, Southern Subregional Contest
Date:	Saratov, October 7, 2004

<|response|>
## 1) Abridged problem statement

You are given **N** rectangles (pies), each with **two candle points**. You must pick **exactly K** pies such that the **sum of their areas is maximum** (if multiple sets of K give the same maximum sum, any of them might be delivered).

For each delivered pie, it will be eaten only if it is possible to make **one straight cut** that:

- splits the rectangle into **two equal-area parts**,
- puts the **two candles in different parts**,
- and the cut **does not pass through a candle**.

If a pie is eatable, the optimist’s share is **half of that pie’s area**; otherwise it contributes **0**.

Output (with 3 decimals):

- **Pessimist**: minimum possible optimist total among all maximum-area choices of K pies.
- **Optimist**: maximum possible optimist total among all maximum-area choices of K pies.

Constraints: `N ≤ 1000`, `K ≤ 10`.

---

## 2) Key observations needed to solve the problem

### A. Equal-area cut of a rectangle
A rectangle is **centrally symmetric**, so:

> A straight line cuts a rectangle into two equal areas **iff** the line passes through the rectangle’s **center**.

So any valid cut must pass through the center `O`.

### B. When can a line through the center separate the two candles?
Let candles be points `X, Y`. Consider vectors from the center:
- `p = X - O`
- `q = Y - O`

A line through `O` separates `X` and `Y` strictly (and does not pass through either candle) iff there exists some line through `O` such that `p` and `q` lie in **opposite open half-planes**.

This is **impossible** exactly in these cases:

1. **A candle at the center**: `p = 0` or `q = 0`  
   Any line through `O` passes through that candle → forbidden.

2. **Candles on the same ray from the center**: `p` and `q` are collinear and point in the same direction  
   Then no line through `O` can strictly separate them.

Equivalently, the rectangle is **cuttable** iff:
- `p × q != 0` (not collinear), **or**
- they are collinear but opposite directions: `p · q < 0`

So the check is:
```text
cuttable ⇔ |p×q| > eps  OR  p·q < -eps
```

### C. Which K pies are chosen to maximize total area?
Sort pies by area descending. Let `T = area of the K-th pie`.

- All pies with `area > T` are **forced** in any maximum-area selection.
- Pies with `area < T` are **never** selected.
- Only pies with `area == T` are “tie pies”; different maximum-area selections differ only in which of these tie pies are taken.

Thus, pessimist/optimist uncertainty exists **only** inside the `area == T` group.

---

## 3) Full solution approach

### Step 1: For each pie, compute:
1) **Area** of the rectangle  
Input corner order is arbitrary. Do:
- compute center as the average of 4 corners,
- sort corners by polar angle around the center,
- apply shoelace formula.

2) **Cuttable flag** using candle vectors `p, q` from the center:
- `cuttable = (abs(cross(p,q)) > EPS) or (dot(p,q) < -EPS)`

Store `(area, cuttable)`.

### Step 2: Identify forced pies and the tie group
Sort all pies by `area` decreasing.

If `K == 0`, answer is `0 0`.

Let `T = pies[K-1].area`.

Compute:
- `fixed = sum(area/2 for forced pies with area > T that are cuttable)`  
  (forced pies are always selected; non-cuttable forced pies contribute 0)
- `above = count(area > T)`
- among pies with `area == T`:
  - `eq_total`
  - `eq_cut` (cuttable count)
  - `eq_noncut = eq_total - eq_cut`
- `need = K - above` (how many pies must be chosen from the tie group)

### Step 3: Best and worst possible optimist share
All tie pies have the same area `T`.

- **Optimist (best case)** picks as many cuttable among the `need` as possible:
  - cuttable picked = `min(need, eq_cut)`
  - contribution = `min(need, eq_cut) * T/2`

- **Pessimist (worst case)** tries to minimize cuttable picked, using non-cuttable first:
  - cuttable forced = `max(0, need - eq_noncut)`
  - contribution = `max(0, need - eq_noncut) * T/2`

Final answers:
- `pes = fixed + max(0, need - eq_noncut) * T/2`
- `opt = fixed + min(need, eq_cut) * T/2`

Complexity: `O(N log N)` (sorting), fits easily.

---

## 4) C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

static const double EPS = 1e-9;

struct Pt {
    double x, y;
    Pt() : x(0), y(0) {}
    Pt(double _x, double _y) : x(_x), y(_y) {}
};

static inline Pt operator+(const Pt& a, const Pt& b) { return Pt(a.x + b.x, a.y + b.y); }
static inline Pt operator-(const Pt& a, const Pt& b) { return Pt(a.x - b.x, a.y - b.y); }
static inline Pt operator/(const Pt& a, double k) { return Pt(a.x / k, a.y / k); }

static inline double cross(const Pt& a, const Pt& b) { return a.x * b.y - a.y * b.x; }
static inline double dot(const Pt& a, const Pt& b) { return a.x * b.x + a.y * b.y; }
static inline double angle_of(const Pt& v) { return atan2(v.y, v.x); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    // Store (area, cuttable)
    vector<pair<double,bool>> pies;
    pies.reserve(N);

    for (int i = 0; i < N; i++) {
        // Read 4 corners and 2 candles
        int ax, ay, bx, by, cx, cy, dx, dy;
        int x1, y1, x2, y2;
        cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy >> x1 >> y1 >> x2 >> y2;

        Pt A(ax, ay), B(bx, by), C(cx, cy), D(dx, dy);
        Pt X(x1, y1), Y(x2, y2);

        // Rectangle center is average of 4 corners (true for any rectangle)
        Pt O = (A + B + C + D) / 4.0;

        // Sort corners by polar angle around center -> proper polygon order
        array<Pt,4> corners = {A, B, C, D};
        sort(corners.begin(), corners.end(), [&](const Pt& p, const Pt& q){
            return angle_of(p - O) < angle_of(q - O);
        });

        // Shoelace area (via cross sum)
        double s = 0.0;
        for (int j = 0; j < 4; j++) {
            s += cross(corners[j], corners[(j + 1) % 4]);
        }
        double area = fabs(s) / 2.0;

        // Candle vectors from center
        Pt p = X - O;
        Pt q = Y - O;

        // Cuttable iff:
        // 1) not collinear: |p×q| > EPS, OR
        // 2) collinear but opposite directions: p·q < -EPS
        bool cuttable = (fabs(cross(p, q)) > EPS) || (dot(p, q) < -EPS);

        pies.push_back({area, cuttable});
    }

    // If choose 0 pies, both shares are 0.
    if (K == 0) {
        cout << fixed << setprecision(3) << 0.0 << " " << 0.0 << "\n";
        return 0;
    }

    // Sort pies by area descending to characterize all maximum-total-area choices.
    sort(pies.begin(), pies.end(), [&](auto &a, auto &b){
        return a.first > b.first;
    });

    // Threshold area T is the K-th pie's area.
    double T = pies[K - 1].first;

    // fixed_share: contribution from pies with area > T (forced in every max-area selection)
    double fixed_share = 0.0;
    int above = 0;

    // Count within equality group (area == T)
    int eq_total = 0, eq_cut = 0;

    for (auto &[area, cut] : pies) {
        if (area > T + EPS) {
            above++;
            if (cut) fixed_share += area / 2.0;
        } else if (fabs(area - T) <= EPS) {
            eq_total++;
            if (cut) eq_cut++;
        }
    }

    int need = K - above;               // must pick this many from the ==T group
    int eq_noncut = eq_total - eq_cut;

    // Best case: choose as many cuttable among equals as possible
    double opt = fixed_share + (double)min(need, eq_cut) * (T / 2.0);

    // Worst case: choose as many non-cuttable among equals as possible
    double pes = fixed_share + (double)max(0, need - eq_noncut) * (T / 2.0);

    cout << fixed << setprecision(3) << pes << " " << opt << "\n";
    return 0;
}
```

---

## 5) Python implementation with detailed comments

```python
import sys
import math

EPS = 1e-9

def cross(ax, ay, bx, by):
    return ax * by - ay * bx

def dot(ax, ay, bx, by):
    return ax * bx + ay * by

def angle(dx, dy):
    return math.atan2(dy, dx)

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    k = int(next(it))

    pies = []  # list of (area, cuttable)

    for _ in range(n):
        ax, ay = int(next(it)), int(next(it))
        bx, by = int(next(it)), int(next(it))
        cx, cy = int(next(it)), int(next(it))
        dx, dy = int(next(it)), int(next(it))
        x1, y1 = int(next(it)), int(next(it))
        x2, y2 = int(next(it)), int(next(it))

        # Center of rectangle = average of 4 corners
        ox = (ax + bx + cx + dx) / 4.0
        oy = (ay + by + cy + dy) / 4.0

        # Sort corners around center to form polygon boundary order
        corners = [(ax, ay), (bx, by), (cx, cy), (dx, dy)]
        corners.sort(key=lambda p: angle(p[0] - ox, p[1] - oy))

        # Shoelace area via cross sum
        s = 0.0
        for i in range(4):
            xA, yA = corners[i]
            xB, yB = corners[(i + 1) % 4]
            s += cross(xA, yA, xB, yB)
        area = abs(s) / 2.0

        # Vectors from center to candles
        px, py = x1 - ox, y1 - oy
        qx, qy = x2 - ox, y2 - oy

        # Cuttable iff not collinear OR opposite directions when collinear
        c = cross(px, py, qx, qy)
        d = dot(px, py, qx, qy)
        cuttable = (abs(c) > EPS) or (d < -EPS)

        pies.append((area, cuttable))

    # If we pick 0 pies, both answers are 0.
    if k == 0:
        print(f"{0.0:.3f} {0.0:.3f}")
        return

    # Sort by area descending (maximizing total area)
    pies.sort(key=lambda t: t[0], reverse=True)

    # Threshold area (K-th largest)
    T = pies[k - 1][0]

    fixed_share = 0.0  # forced contribution from pies with area > T
    above = 0

    eq_total = 0
    eq_cut = 0

    for area, cut in pies:
        if area > T + EPS:
            above += 1
            if cut:
                fixed_share += area / 2.0
        elif abs(area - T) <= EPS:
            eq_total += 1
            if cut:
                eq_cut += 1

    need = k - above
    eq_noncut = eq_total - eq_cut

    # Optimist: maximize number of cuttable pies chosen among equals
    opt = fixed_share + min(need, eq_cut) * (T / 2.0)

    # Pessimist: minimize number of cuttable pies chosen among equals
    pes = fixed_share + max(0, need - eq_noncut) * (T / 2.0)

    print(f"{pes:.3f} {opt:.3f}")

if __name__ == "__main__":
    solve()
```

