The Butcher (Codeforces 1820D)
Tags: Implement, two pointers

Anton plays his favorite game "Defense of The Ancients 2" for his favorite hero — The Butcher. Now he wants to make his own dinner. To do this he will take a rectangle of height $$$h$$$ and width $$$w$$$, then make a vertical or horizontal cut so that both resulting parts have integer sides. After that, he will put one of the parts in the box and cut the other again, and so on.More formally, a rectangle of size $$$h \times w$$$ can be cut into two parts of sizes $$$x \times w$$$ and $$$(h - x) \times w$$$, where $$$x$$$ is an integer from $$$1$$$ to $$$(h - 1)$$$, or into two parts of sizes $$$h \times y$$$ and $$$h \times (w - y)$$$, where $$$y$$$ is an integer from $$$1$$$ to $$$(w - 1)$$$.He will repeat this operation $$$n - 1$$$ times, and then put the remaining rectangle into the box too. Thus, the box will contain $$$n$$$ rectangles, of which $$$n - 1$$$ rectangles were put in the box as a result of the cuts, and the $$$n$$$-th rectangle is the one that the Butcher has left after all $$$n - 1$$$ cuts.Unfortunately, Butcher forgot the numbers $$$h$$$ and $$$w$$$, but he still has $$$n$$$ rectangles mixed in random order. Note that Butcher didn't rotate the rectangles, but only shuffled them. Now he wants to know all possible pairs $$$(h, w)$$$ from which this set of rectangles can be obtained. And you have to help him do it!It is guaranteed that there exists at least one pair $$$(h, w)$$$ from which this set of rectangles can be obtained.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of rectangles obtained.The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^6$$$) — the height and width of the $$$i$$$-th rectangle.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, on the first line output a single integer $$$m$$$ — the number of pairs $$$(h, w)$$$ denoting the sizes of rectangles from which the given rectangles can be obtained. Two rectangles are considered different if they have different heights or widths.On each of the following $$$m$$$ lines print output integers $$$h_i$$$ and $$$w_i$$$ — the height and width of the rectangle from which the given rectangles can be obtained. You can output the rectangles in any order.

Note: In the first test case, Butcher could only have a rectangle of size $$$4 \times 5$$$. Then the cuts could look like this (first the green cut was made, then the red one):  In the second test case, Butcher could have either a rectangle of $$$1 \times 3$$$ or $$$3 \times 1$$$. The cuts would have looked like this (first the green cut was made, then the red cut):  In the third test case, Butcher did not make any cuts, so the rectangle is $$$10 \times 10$$$.

Sample Inputs:
4
3
1 2
3 5
1 3
3
1 1
1 1
1 1
1
10 10
4
3 2
5 5
2 2
8 7

Sample Outputs:
1
4 5
2
1 3
3 1
1
10 10
1
13 7

Solution (Python):
import collections

def ispossible(x, y, a):
    f = collections.defaultdict(set)
    g = collections.defaultdict(set)
    for (i, (u, v)) in enumerate(a):
        f[u].add(i)
        g[v].add(i)
    for i in range(n):
        if x in f and len(f[x]) > 0:
            z = f[x].pop()
            y -= a[z][1]
            g[a[z][1]].remove(z)
        elif y in g and len(g[y]) > 0:
            z = g[y].pop()
            x -= a[z][0]
            f[a[z][0]].remove(z)
        else:
            return False
    return True
t = int(input())
for _ in range(t):
    n = int(input())
    mx = 0
    my = 0
    s = 0
    a = []
    for i in range(n):
        (x, y) = map(int, input().split())
        if x > mx:
            mx = x
        if y > my:
            my = y
        s += x * y
        a.append((x, y))
    ans = set()
    if s % mx == 0 and ispossible(mx, s // mx, a):
        ans.add((mx, s // mx))
    if s % my == 0 and ispossible(s // my, my, a):
        ans.add((s // my, my))
    print(len(ans))
    for a in ans:
        print(*a)

Solution (Python):
import collections

def ispossible(x, y, a):
    f = collections.defaultdict(set)
    g = collections.defaultdict(set)
    for (i, (u, v)) in enumerate(a):
        f[u].add(i)
        g[v].add(i)
    for i in range(n):
        if x in f and len(f[x]) > 0:
            z = f[x].pop()
            y -= a[z][1]
            g[a[z][1]].remove(z)
        elif y in g and len(g[y]) > 0:
            z = g[y].pop()
            x -= a[z][0]
            f[a[z][0]].remove(z)
        else:
            return False
    return True
t = int(input())
for _ in range(t):
    n = int(input())
    mx = 0
    my = 0
    s = 0
    a = []
    for i in range(n):
        (x, y) = map(int, input().split())
        if x > mx:
            mx = x
        if y > my:
            my = y
        s += x * y
        a.append((x, y))
    ans = set()
    if s % mx == 0 and ispossible(mx, s // mx, a):
        ans.add((mx, s // mx))
    if s % my == 0 and ispossible(s // my, my, a):
        ans.add((s // my, my))
    print(len(ans))
    for a in ans:
        print(*a)

Solution (Python):
from typing import *
Rect = Tuple[int, int]

class OrderedRects:

    def __init__(self, rects: List[Rect]) -> None:
        self._rects_by_h = sorted([(i, h, w) for (i, (h, w)) in enumerate(rects)], key=lambda r: r[1], reverse=True)
        self._rects_by_w = sorted([(i, h, w) for (i, (h, w)) in enumerate(rects)], key=lambda r: r[2], reverse=True)
        self._ih = 0
        self._iw = 0
        self._visited: Set[int] = set()

    def take_highests(self) -> List[Rect]:
        highests: List[Rect] = []
        while self._ih < len(self._rects_by_h):
            current = self._rects_by_h[self._ih]
            if current[0] in self._visited:
                self._ih += 1
                continue
            if highests and current[1] < highests[0][0]:
                break
            self._visited.add(current[0])
            highests.append((current[1], current[2]))
            self._ih += 1
        return highests

    def take_widests(self) -> List[Rect]:
        widests: List[Rect] = []
        while self._iw < len(self._rects_by_w):
            current = self._rects_by_w[self._iw]
            if current[0] in self._visited:
                self._iw += 1
                continue
            if widests and current[2] < widests[0][1]:
                break
            self._visited.add(current[0])
            widests.append((current[1], current[2]))
            self._iw += 1
        return widests

def try_highest_first(rects: List[Rect]) -> Optional[Tuple[int, int]]:
    ordered_rects = OrderedRects(rects)
    highests = ordered_rects.take_highests()
    if not highests:
        return None
    height = highests[0][0]
    width = sum((r[1] for r in highests))
    widests = ordered_rects.take_widests()
    if not widests:
        return (height, width)
    width += widests[0][1]
    remaining_height = height - sum((r[0] for r in widests))
    remaining_width = widests[0][1]
    while True:
        highests = ordered_rects.take_highests()
        if not highests:
            break
        if highests[0][0] != remaining_height:
            return None
        remaining_width -= sum((r[1] for r in highests))
        if remaining_width < 0:
            return None
        widests = ordered_rects.take_widests()
        if not widests:
            break
        if widests[0][1] != remaining_width:
            return None
        remaining_height -= sum((r[0] for r in widests))
        if remaining_height < 0:
            return None
    if remaining_height == 0 or remaining_width == 0:
        return (height, width)
    return None

def try_widests_first(rects: List[Rect]) -> Optional[Tuple[int, int]]:
    ordered_rects = OrderedRects(rects)
    widests = ordered_rects.take_widests()
    if not widests:
        return None
    width = widests[0][1]
    height = sum((r[0] for r in widests))
    highests = ordered_rects.take_highests()
    if not highests:
        return (height, width)
    height += highests[0][0]
    remaining_height = highests[0][0]
    remaining_width = width - sum((r[1] for r in highests))
    while True:
        widests = ordered_rects.take_widests()
        if not widests:
            break
        if widests[0][1] != remaining_width:
            return None
        remaining_height -= sum((r[0] for r in widests))
        if remaining_height < 0:
            return None
        highests = ordered_rects.take_highests()
        if not highests:
            break
        if highests[0][0] != remaining_height:
            return None
        remaining_width -= sum((r[1] for r in highests))
        if remaining_width < 0:
            return None
    if remaining_height == 0 or remaining_width == 0:
        return (height, width)
    return None
for _ in range(int(input())):
    n = int(input())
    rects = []
    for i in range(n):
        (a, b) = map(int, input().split())
        rects.append((a, b))
    ans = {try_highest_first(rects), try_widests_first(rects)}
    ans.discard(None)
    print(len(ans))
    for (h, w) in ans:
        print(f'{h} {w}')