<|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

```cpp
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = double;

struct Point {
    static constexpr coord_t eps = 1e-9;
    static inline const coord_t PI = acos((coord_t)-1.0);

    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrt(norm2()); }
    coord_t angle() const { return atan2(y, x); }

    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }

    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    friend Point circumcenter(const Point& a, const Point& b, const Point& c) {
        Point mid_ab = (a + b) / 2.0;
        Point mid_ac = (a + c) / 2.0;
        Point perp_ab = (b - a).perp();
        Point perp_ac = (c - a).perp();
        return line_line_intersection(
            mid_ab, mid_ab + perp_ab, mid_ac, mid_ac + perp_ac
        );
    }

    friend coord_t arc_area(
        const Point& center, coord_t r, const Point& p1, const Point& p2
    ) {
        coord_t theta1 = (p1 - center).angle();
        coord_t theta2 = (p2 - center).angle();
        if(theta2 < theta1 - eps) {
            theta2 += 2 * PI;
        }

        coord_t d_theta = theta2 - theta1;
        coord_t cx = center.x, cy = center.y;
        coord_t area = r * cx * (sin(theta2) - sin(theta1)) -
                       r * cy * (cos(theta2) - cos(theta1)) + r * r * d_theta;
        return area / 2.0;
    }

    friend vector<Point> intersect_circles(
        const Point& c1, coord_t r1, const Point& c2, coord_t r2
    ) {
        Point d = c2 - c1;
        coord_t dist = d.norm();

        if(dist > r1 + r2 + eps || dist < abs(r1 - r2) - eps || dist < eps) {
            return {};
        }

        coord_t a = (r1 * r1 - r2 * r2 + dist * dist) / (2 * dist);
        coord_t h_sq = r1 * r1 - a * a;
        if(h_sq < -eps) {
            return {};
        }
        if(h_sq < 0) {
            h_sq = 0;
        }
        coord_t h = sqrt(h_sq);

        Point mid = c1 + d.unit() * a;
        Point perp_dir = d.perp().unit();

        if(h < eps) {
            return {mid};
        }
        return {mid + perp_dir * h, mid - perp_dir * h};
    }

    friend optional<Point> intersect_ray_segment(
        const Point& ray_start, const Point& ray_through, const Point& seg_a,
        const Point& seg_b
    ) {
        Point ray_dir = ray_through - ray_start;
        if(ray_dir.norm2() < Point::eps) {
            return {};
        }
        Point seg_dir = seg_b - seg_a;
        coord_t denom = ray_dir ^ seg_dir;
        if(fabs(denom) < eps) {
            return {};
        }
        coord_t t = ((seg_a - ray_start) ^ seg_dir) / denom;
        if(t < eps) {
            return {};
        }
        coord_t s = ((seg_a - ray_start) ^ ray_dir) / denom;
        if(s < eps || s > 1 - eps) {
            return {};
        }
        return ray_start + ray_dir * t;
    }
};

int n, k;
vector<tuple<Point, Point, Point, Point, Point, Point>> cakes;

void read() {
    cin >> n >> k;
    cakes.resize(n);
    for(auto& [a, b, c, d, x, y]: cakes) {
        int ax, ay, bx, by, cx, cy, dx, dy, xx, xy, yx, yy;
        cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy >> xx >> xy >> yx >>
            yy;
        a = Point(ax, ay);
        b = Point(bx, by);
        c = Point(cx, cy);
        d = Point(dx, dy);
        x = Point(xx, xy);
        y = Point(yx, yy);
    }
}

void solve() {
    // A rectangle is centrally symmetric, so any equal-area bisecting line
    // must pass through its center. We need such a line that separates the two
    // candles without passing through either. This fails in exactly two cases:
    // (1) a candle sits at the center (every line through center hits it), or
    // (2) both candles lie on the same ray from the center (no line through
    //     the center can put them on opposite sides).
    //
    // Now we want to pick K pies maximizing total area. Among all such optimal
    // selections, the pessimist takes the one minimizing the total "eatable"
    // (cuttable) area, and the optimist maximizes it. Each person gets half of
    // each cuttable pie. Since all optimal selections share the same total area
    // and differ only in pies at the threshold value, we just need to count how
    // many cuttable vs non-cuttable pies sit at the boundary and greedily pick.

    vector<pair<coord_t, bool>> pies(n);

    for(int i = 0; i < n; i++) {
        auto& [a, b, c, d, x, y] = cakes[i];
        Point center = (a + b + c + d) / 4.0;

        vector<Point> corners = {a, b, c, d};
        sort(
            corners.begin(), corners.end(),
            [&](const Point& p, const Point& q) {
                return (p - center).angle() < (q - center).angle();
            }
        );
        coord_t area = 0;
        for(int j = 0; j < 4; j++) {
            area += corners[j] ^ corners[(j + 1) % 4];
        }
        area = abs(area) / 2.0;

        Point px = x - center, py = y - center;
        bool cuttable = abs(px ^ py) > 1e-9 || (px * py) < -1e-9;

        pies[i] = {area, cuttable};
    }

    sort(pies.begin(), pies.end(), [](auto& a, auto& b) {
        return a.first > b.first;
    });

    if(k == 0) {
        cout << fixed << setprecision(3) << 0.0 << " " << 0.0 << "\n";
        return;
    }

    coord_t threshold = pies[k - 1].first;
    coord_t fixed_area = 0;
    int above = 0, cuttable_eq = 0, total_eq = 0;

    for(auto& [area, cut]: pies) {
        if(area > threshold + 1e-9) {
            above++;
            if(cut) {
                fixed_area += area / 2.0;
            }
        } else if(abs(area - threshold) < 1e-9) {
            total_eq++;
            if(cut) {
                cuttable_eq++;
            }
        }
    }

    int need = k - above;
    int non_cuttable_eq = total_eq - cuttable_eq;

    coord_t opt = fixed_area + min(need, cuttable_eq) * threshold / 2.0;
    coord_t pes = fixed_area + max(0, need - non_cuttable_eq) * threshold / 2.0;

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

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation

```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() -> None:
    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):
        # Read rectangle corners and two candles (all ints)
        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))
        xx, xy = int(next(it)), int(next(it))
        yx, yy = 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 by polar angle around center to get consistent polygon order
        corners = [(ax, ay), (bx, by), (cx, cy), (dx, dy)]
        corners.sort(key=lambda p: angle(p[0] - ox, p[1] - oy))

        # Shoelace via cross sum
        s = 0.0
        for i in range(4):
            x1, y1 = corners[i]
            x2, y2 = corners[(i + 1) % 4]
            s += cross(x1, y1, x2, y2)
        area = abs(s) / 2.0

        # Vectors from center to candles
        px, py = xx - ox, xy - oy
        qx, qy = yx - ox, yy - oy

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

        pies.append((area, cuttable))

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

    if k == 0:
        print(f"{0.0:.3f} {0.0:.3f}")
        return

    threshold = pies[k - 1][0]

    fixed_area = 0.0    # forced pies above threshold (optimist share)
    above = 0           # count of pies with area > threshold
    total_eq = 0        # count of pies with area == threshold
    cuttable_eq = 0     # among equals, how many cuttable

    for area, cut in pies:
        if area > threshold + EPS:
            above += 1
            if cut:
                fixed_area += area / 2.0
        elif abs(area - threshold) < EPS:
            total_eq += 1
            if cut:
                cuttable_eq += 1

    need = k - above
    non_cuttable_eq = total_eq - cuttable_eq

    # Best case: pick as many cuttable among the equals
    opt = fixed_area + min(need, cuttable_eq) * threshold / 2.0

    # Worst case: pick non-cuttable first; forced cuttable are what's left
    pes = fixed_area + max(0, need - non_cuttable_eq) * threshold / 2.0

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

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