Problem: cake_cutting_committee (2020 finals)

Melody is preparing a cake for a very special occasion. She's starting off with a square cake, though she'd like it cut down into a more unique shape. When viewed from above, it can be represented as a square on a 2D plane, with opposite corners at coordinates \((0, 0)\) and \((S, S)\).

Out of countless contenders, Melody has interviewed \(N\) certified cake-cutting consultants, asking how the cake should be cut down. The \(i\)th consultant, who has a competence value of \(C_i\), has proposed that two cuts should be performed: the first being a line segment between coordinates \((X_{i,1}, Y_{i,1})\) and \((X_{i,2}, Y_{i,2})\), and the second between \((X_{i,3}, Y_{i,3})\) and \((X_{i,4}, Y_{i,4})\). Each of these four points is exactly on a side of the cake (but not on a corner), the two points describing each line segment are not on the same side of the cake, and the two line segments do not share any points in common (in other words, they don't intersect nor have any equal endpoints). Therefore, the two cuts would split the cake into three non-empty polygonal sections. Of those, the middle section (the one between the two cuts) would become their **proposed cake shape**, with the other two sections discarded.

For example, the following diagram illustrates a cake with \(S = 10\) and a consultant's pair of proposed cuts (from \((4, 10)\) to \((2, 0)\) and from \((0, 9)\) to \((2, 10)\)), with their resulting proposed cake shape highlighted in blue:

{{PHOTO_ID:186542789854750}}

Melody wants to hire one or more of the consultants to form a committee, whose members will then deliberate on the final shape of the cake. That is, she calls for a completely competent consulting committee capable of coming to a consensus on a commendable cake-cutting configuration. Clearly.

She wants the sum of the hired consultants' competence values to be as large as possible, no matter how many of them she has to hire. However, she won't allow a pair of consultants to both be part of the committee if their cake-cutting proposals *fundamentally differ*, which is the case if their proposed cake shapes do not share any points in common (in other words, if those two polygons are entirely disjoint, including at their edges and vertices).

For example, the following diagram additionally includes another consultant's pair of proposed cuts (from (7, 10) to (10, 7) and from (10, 5) to (5, 10)), with their proposed cake shape highlighted in red. Since these two proposed cake shapes do not overlap at all, the two proposals fundamentally differ, meaning that if one of these consultants is hired, the other cannot also be hired:

{{PHOTO_ID:3047534892140325}}

On the other hand, each of the following cakes features a pair of proposals which do not fundamentally differ, due to the proposed cake shapes sharing at least one point in common (meaning that, for each cake, the two consultants could be hired together):

{{PHOTO_ID:139722534273576}}

Help Melody determine the maximum combined competence of consultants who can form the committee, such that no two of them have fundamentally differing cake-cutting proposals.

# Constraints

\(1 \le T \le 80\)
\(1 \le N \le 800\)
\(2 \le S \le 100,000,000\)
\(1 \le C_i \le 500,000\)
\(0 \le X_{i,j}, Y_{i,j} \le S\)

The sum of \(N\) across all special occasions is at most 20,000.

# Input

Input begins with an integer \(T\), the number of special occasions. For each occasion, there are \(N + 1\) lines. The first line contains 2 space-separated integers, \(S\) and \(N\). \(N\) lines follow, the \(i\)th of which contains the 9 space-separated integers \(C_i\), \(X_{i,1}\), \(Y_{i,1}\), \(X_{i,2}\), \(Y_{i,2}\), \(X_{i,3}\), \(Y_{i,3}\), and \(X_{i,4}\), \(Y_{i,4}\).


# Output

For the \(i\)th special occasion, print a line containing *"Case #i: "*, followed by a single integer, the maximum combined competence of cake-cutting consultants who can form the committee.


# Explanation of Sample

The first cake (along with the consultants' proposed cake shapes) looks as follows:

{{PHOTO_ID:2722961511304050}}

The 1st and 2nd consultants can't both be hired together, but either can be hired alongside the 3rd consultant. So, the best Melody can do is to hire the 2nd and 3rd consultants for a combined competence of \(30 + 40 = 70\).

The second cake looks as follows:

{{PHOTO_ID:408936830244710}}

Melody can hire all three consultants.

The third cake looks as follows:

{{PHOTO_ID:386528679257402}}

The fourth cake looks as follows:

{{PHOTO_ID:863939674419710}}

The fifth cake looks as follows:

{{PHOTO_ID:424906348725741}}


Sample input:
7
10 3
20 0 4 10 4 0 6 10 6
30 0 8 10 8 0 9 10 9
40 2 0 2 10 5 0 5 10
4 3
10 0 1 1 0 0 2 2 0
20 0 2 2 4 0 3 1 4
30 2 0 2 4 3 0 3 4
4 4
10 0 1 1 0 0 2 2 0
20 4 2 2 4 4 3 3 4
30 0 2 2 4 0 3 1 4
40 4 1 3 0 4 2 2 0
5 4
1 0 1 5 1 0 2 5 2
2 0 2 5 2 0 3 5 3
4 0 3 5 3 0 4 5 4
8 0 4 5 4 0 1 5 1
10 5
3 4 0 0 3 6 0 8 10
4 7 10 10 7 10 5 5 10
6 4 10 2 0 0 9 2 10
3 10 5 6 0 9 0 10 4
1 0 4 10 5 10 7 0 6
10000 15
964 0 9688 10000 9757 0 5290 6888 0
1121 0 1389 1707 0 10000 4897 6073 10000
480 52 0 7636 10000 0 7970 5894 10000
232 3924 0 4373 10000 2183 10000 1472 0
133 2471 10000 0 4074 5240 10000 10000 5064
706 9853 10000 10000 6154 0 1824 395 10000
180 0 545 10000 2644 10000 3667 1372 10000
253 2305 0 0 1825 10000 7597 7210 0
758 9154 0 0 1748 0 9591 10000 9017
603 10000 3697 0 7106 3861 10000 0 8408
793 9724 0 10000 6555 0 3725 4425 10000
877 8090 10000 6852 0 10000 5453 8854 0
583 10000 2565 7605 0 0 6412 6778 0
1103 5303 10000 0 7918 0 3908 1146 0
86 8641 0 9846 10000 0 5456 5530 0
4000 30
119 4000 959 1713 0 99 0 0 773
58 414 4000 2804 0 4000 3461 2754 4000
282 2913 4000 0 2780 4000 1625 3427 0
244 4000 3384 46 4000 793 0 0 1333
232 1245 4000 0 2659 939 0 1380 4000
423 3556 0 2059 4000 2496 4000 4000 2941
55 2453 4000 4000 1446 1354 4000 1001 0
345 2992 0 0 237 3787 4000 3778 0
208 0 1081 147 0 241 4000 0 2018
88 4000 3288 0 1558 4000 3290 0 3177
309 1190 4000 0 3160 4000 2664 2173 0
400 1470 0 1295 4000 3021 0 4000 3716
408 0 3725 3407 4000 3474 4000 0 2548
154 59 4000 1923 0 2269 4000 4000 1075
221 357 0 3896 4000 0 1000 2862 4000
20 4000 1427 3506 0 2650 4000 4000 1776
333 2773 4000 4000 1978 3608 0 1714 4000
144 0 3360 85 0 4000 2253 1248 4000
522 2002 0 0 3704 0 3787 1289 4000
387 1556 4000 4000 2710 826 0 4000 44
405 0 3826 3448 0 4000 1888 519 4000
89 3409 4000 4000 1216 0 780 3245 4000
448 1533 4000 3501 0 3469 0 0 854
118 592 4000 0 1908 4000 773 2660 4000
372 0 1669 3074 0 2879 4000 4000 3636
283 4000 3549 2078 4000 4000 2056 631 0
446 0 3575 411 4000 962 4000 4000 133
484 0 147 2755 0 1001 4000 0 2018
139 0 251 3229 0 4000 3642 0 2816
151 4000 1647 3562 4000 3122 4000 2113 0


Sample output:
Case #1: 70
Case #2: 60
Case #3: 60
Case #4: 14
Case #5: 11
Case #6: 8160
Case #7: 7207


Solution: We can number the possible positions of line segment endpoints from \(1\) to \(4(N-1)\) in clockwise order around the edge of the square, and then simply map all of the given line segment endpoints to these indices, noting that only their relative order is relevant for determining which proposed cake shapes overlap with one another.

It's possible to show that, for any valid set of proposed cake shapes, there must exist at least one *key line segment* amongst them such that every polygon in the set overlaps with that line segment. We'll therefore consider all \(2N\) possible key line segments.

For a given key line segment, each polygon either doesn't overlap with it at all (and so should be ignored), overlaps with all of it (and so may always be used), or overlaps with only part of it. For polygons falling into this final category, we're interested in the maximum combined value of any set of them such that each pair of them overlaps.

The key line segment splits the full set of possible endpoint indices into two sections, which we'll call the X and Y sections. We can map each polygon's endpoints to new indices along these two sections, both numbered starting from the same ("first") endpoint of the key line segment (meaning that one section's sequence of indices is equivalent to increasing original indices, while the other section's is equivalent to decreasing original indices). If a polygon has 3 endpoints in one section and 1 endpoint in the other (as opposed to 2 in each), then we'll shift one of them over to one of the key line segment's endpoints without changing which other polygons it overlaps with.

The result is that, for each line segment of each polygon, one endpoint will have been mapped to a new index in the X section, with the other mapped to a new index in the Y section. This allows us to represent each polygon by a pair of intervals \([x_1, x_2]\) and \([y_1, y_2]\) (consisting of its two X section indices and its two Y section indices, respectively). With this representation, we can then observe that a pair of polygons don't overlap if and only one of the polygons' X and Y intervals are both strictly to the right (or strictly to the left) of the other polygon's respective X and Y intervals.

If we now visualize each such polygon as a rectangle on a 2D plane, with coordinates based on its X and Y intervals (in particular, with lower-left corner \((x_1, y_1)\) and upper-right corner \((x_1, y_1)\)), we're interested in the maximum combined value of any set of them such that no rectangle is strictly both above and to the right of any other rectangle. This may be accomplished in \(O(N log(N))\) time with a line sweep over the x-coordinates. We'll let \(M_y\) be the maximum combined value of a valid set of rectangles encountered so far, such that the lowest of their top-right corners encountered so far has y-coordinate `y`, and maintain this with the help of a segment tree:

- When we encounter the left edge of a rectangle with bottom edge `y_1`, we should increase each of \(M_{y_1..\infty}\) by that rectangle's value (as this rectangle may be added to any such set).
- When we encounter the right edge of a rectangle with top edge `y_2`, we should first set \(M_{y_2}\) to \(\max(M_{(y_2+1)..\infty})\) (as including this rectangle in any such set would decrease its lowest top-right corner to \(y_2\)). We should then decrease each of \(M_{(y_2+1)..\infty}\) by that rectangle's value (as this rectangle may no longer be added to any such set).

Repeating the above process for all \(2N\) possible key line segments yields a solution with a time complexity of \(O(N^2 log(N))\) (though a less efficient, \(O(N^3)\) implementation would also suffice).

For further reading, if we consider mapping the line segment endpoint indices to positions around the circumference of a circle instead (essentially treating the original square as a circle), each proposed cake shape is known as a *circle trapezoid*. The intersection graph of these polygons (a graph in which there's an edge between two pieces if and only if they overlap) is then known as a [*circle trapezoid graph*](https://en.wikipedia.org/wiki/Trapezoid_graph#Circle_trapezoid_graphs). The problem of computing the maximum clique weight in such a graph (equivalent to what's asked for in Cake-Cutting Committee), and other related problems, are explored further in [this paper](https://www.sciencedirect.com/science/article/pii/S0166218X96000133?via%3Dihub).


Code: // Cake-Cutting Committee
// Solution by Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (auto i:s)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#define GETCHAR getchar_unlocked

bool Read(int& x) {
  char c, r = 0, n = 0;
  x = 0;
  for (;;) {
    c = GETCHAR();
    if ((c < 0) && (!r))
      return(0);
    if ((c == '-') && (!r))
      n = 1;
    else if ((c >= '0') && (c <= '9'))
      x = x * 10 + c - '0', r = 1;
    else if (r)
      break;
  }
  if (n)
    x = -x;
  return(1);
}

#define LIM 800

#define TVAL int
#define TLAZY int
#define TLIM 4100

TVAL ZERO_VAL = 0;
TLAZY ZERO_LAZY = 0;

struct SegTree
{
  void UpdateValForUpdateOrLazy(TVAL& a, TLAZY v)
  {
    a += v;
  }

  void UpdateLazyForUpdateOrLazy(TLAZY& a, TLAZY v)
  {
    a += v;
  }

  TVAL CombVals(TVAL v1, TVAL v2)
  {
    return(max(v1, v2));
  }

  int N, sz;
  TVAL tree[TLIM];
  TLAZY lazy[TLIM];

  SegTree() {}

  SegTree(int _N)
  {
    Init(_N);
  }

  void Init(int _N)
  {
    N = _N;
    for (sz = 1; sz < N; sz <<= 1);
    Clear();
  }

  void Clear()
  {
    int i;
    Fox(i, sz << 1)
      tree[i] = ZERO_VAL;
    Fox(i, sz << 1)
      lazy[i] = ZERO_LAZY;
  }

  void Prop(int i)
  {
    TLAZY v = lazy[i];
    lazy[i] = ZERO_LAZY;
    UpdateValForUpdateOrLazy(tree[i], v);
    if (i < sz)
    {
      int c1 = i << 1, c2 = c1 + 1;
      UpdateLazyForUpdateOrLazy(lazy[c1], v);
      UpdateLazyForUpdateOrLazy(lazy[c2], v);
    }
  }

  void Comp(int i)
  {
    int c1 = i << 1, c2 = c1 + 1;
    tree[i] = CombVals(tree[c1], tree[c2]);
  }

  TVAL Query(
    int a, int b,
    int i = 1, int r1 = 0, int r2 = -1
  ) {
    if (r2 < 0)
    {
      Max(a, 0);
      Min(b, sz - 1);
      if (a > b)
        return ZERO_VAL;
      r2 = sz - 1;
    }
    Prop(i);
    if (a <= r1 && r2 <= b)
      return(tree[i]);
    int m = (r1 + r2) >> 1, c = i << 1;
    TVAL ret = ZERO_VAL;
    if (a <= m)
      ret = CombVals(ret, Query(a, b, c, r1, m));
    if (b > m)
      ret = CombVals(ret, Query(a, b, c + 1, m + 1, r2));
    return(ret);
  }

  void Update(
    int a, int b,
    TLAZY v,
    int i = 1, int r1 = 0, int r2 = -1
  ) {
    if (r2 < 0)
    {
      Max(a, 0);
      Min(b, sz - 1);
      if (a > b)
        return;
      r2 = sz - 1;
    }
    Prop(i);
    if (a <= r1 && r2 <= b)
    {
      UpdateLazyForUpdateOrLazy(lazy[i], v);
      Prop(i);
      return;
    }
    int m = (r1 + r2) >> 1, c = i << 1;
    if (a <= m)
      Update(a, b, v, c, r1, m);
    if (b > m)
      Update(a, b, v, c + 1, m + 1, r2);
    Prop(c), Prop(c + 1), Comp(i);
  }
};

struct Event
{
  int x, y1, y2, c;
  bool s;
};

const bool operator<(const Event& a, const Event& b)
{
  return(mp(a.x, !a.s) < mp(b.x, !b.s));
}

int S, N;
int C[LIM], P[LIM][4];

bool IsBetween(int a, int b, int p, bool ex)
{
  if (b < a)
    b += INF;
  if (p < a)
    p += INF;
  return ex ? a < p && p < b : a <= p && p <= b;
}

int GetPosAfter(int a, int p)
{
  if (p < a)
    p += INF;
  return(p - a);
}

int SolveForLine(vector<int> h)
{
  int i, j, s;
  // compare all pieces against dividing line, and assemble line sweep events
  int base = 0;
  vector<int> CY;
  vector<Event> E;
  Fox(i, N)
  {
    // full intersection?
    if (
      (IsBetween(P[i][0], P[i][2], h[0], 0) || IsBetween(P[i][3], P[i][1], h[0], 0)) &&
      (IsBetween(P[i][0], P[i][2], h[1], 0) || IsBetween(P[i][3], P[i][1], h[1], 0))
      )
    {
      base += C[i];
      continue;
    }
    // look for orientation of line segments such that at least one spans crosses from the 1st to the 2nd half
    Fox(s, 2)
    {
      int p[4];
      memcpy(p, P[i], sizeof(p));
      if (s)
        reverse(p, p + 4);
      // check which points are on their required halves
      bool bx[2], by[2];
      Fox(j, 2)
      {
        bx[j] = IsBetween(h[0], h[1], p[j * 2], 0);
        by[j] = IsBetween(h[1], h[0], p[j * 2 + 1], 0);
      }
      // neither line segment is entirely valid?
      if ((!bx[0] || !by[0]) && (!bx[1] || !by[1]))
        continue;
      assert(bx[0] + by[0] + bx[1] + by[1] >= 3); // other one must be at least half-valid
      // map points to positions on their halves
      int x[2], y[2];
      Fox(j, 2)
      {
        x[j] = bx[j] ? GetPosAfter(h[0], p[j * 2]) : 2 * INF * (j ? 1 : -1);
        y[j] = by[j] ? -GetPosAfter(h[1], p[j * 2 + 1]) : 2 * INF * (j ? 1 : -1);
      }
      assert(x[0] < x[1] && y[0] < y[1]);
      E.pb({ x[0], y[0], y[1], C[i], 1 });
      E.pb({ x[1], y[0], y[1], C[i], 0 });
      CY.pb(y[0]), CY.pb(y[1]);
      break;
    }
  }
  // compress Y-coordinates
  sort(All(CY));
  int K = unique(All(CY)) - CY.begin();
  CY.resize(K);
  // line sweep
  SegTree ST(K);
  sort(All(E));
  Foxen(e, E)
  {
    e.y1 = lower_bound(All(CY), e.y1) - CY.begin();
    e.y2 = lower_bound(All(CY), e.y2) - CY.begin();
    // left edge of a rectangle?
    if (e.s)
    {
      ST.Update(e.y1, K - 1, e.c);
      continue;
    }
    // right edge of a rectangle
    ST.Update(e.y2, e.y2, ST.Query(e.y2, K - 1) - ST.Query(e.y2, e.y2));
    ST.Update(e.y2 + 1, K - 1, -e.c);
  }
  return(base + ST.Query(0, K - 1));
}

int ProcessCase()
{
  int i, j;
  // input
  Read(S), Read(N);
  Fox(i, N)
  {
    Read(C[i]);
    Fox(j, 4)
    {
      int x, y;
      Read(x), Read(y);
      if (!x)
        P[i][j] = y;
      else if (y == S)
        P[i][j] = S + x;
      else if (x == S)
        P[i][j] = 3 * S - y;
      else
        P[i][j] = 4 * S - x;
    }
    // normalize lines
    if (IsBetween(P[i][1], P[i][0], P[i][2], 1))
      swap(P[i][0], P[i][1]);
    if (IsBetween(P[i][2], P[i][3], P[i][0], 1))
      swap(P[i][2], P[i][3]);
  }
  // consider all possible dividing lines
  int ans = 0;
  Fox(i, N)
  {
    Fox(j, 2)
      Max(ans, SolveForLine({ P[i][j * 2], P[i][j * 2 + 1] }));
  }
  return(ans);
}

int main()
{
  int T, t;
  Read(T);
  Fox1(t, T)
    printf("Case #%d: %d\n", t, ProcessCase());
  return(0);
}