p267.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;
}

=================
p267.in1
======================
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

=================
statement.txt
======================
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

=================
p267.ans1
======================
8.000 16.000


=================
