Histograms

A histogram represents a data distribution. Here a histogram of width $W$ is given by an even-length sequence of points

$(x_0, y_1),(x_1, y_1),(x_1, y_2),(x_2, y_2),\ldots,(x_{N/2-1}, y_{N/2}),(x_{N/2}, y_{N/2})$

in the plane. Each adjacent pair shares an $x$ or a $y$ coordinate, and horizontal and vertical segments alternate.

The shape must satisfy:

1. $x_0 = 0$
2. $x_{N/2} = W$
3. $x_i < x_{i+1}$
4. $y_i > 0$
5. $y_i \ne y_{i+1}$

For histogram $H$, let $y_H(x)$ be the height on unit interval $\langle x, x+1 \rangle$. Two error measures are used:

$\text{diffcount}(H', H) = \sum_{x=0}^{W-1} \text{diff}(y_H(x), y_{H'}(x)),\quad \text{diff}(y_1,y_2)=0\text{ if }y_1=y_2\text{ else }1$

$\text{abserror}(H', H) = \sum_{x=0}^{W-1} |y_H(x) - y_{H'}(x)|$

Given $H$, a point set $S$, and the measure $G$, find a histogram $H'$ that uses only points from $S$ and minimizes the chosen error.

Line 1: integers $N, M, G$ ($2 \le N \le 100000$, $N$ even, $2 \le M \le 100000$, $1 \le G \le 2$). $G=1$ selects diffcount, $G=2$ selects abserror.

Next $N$ lines: points $(X, Y)$ defining histogram $H$.

Next $M$ lines: points $(X, Y)$ in set $S$. ($0 \le X \le 10^6$, $1 \le Y \le 10^6$)

Line 1: minimum error $D$.

Line 2: even integer $L$, the number of points in the optimal histogram.

Next $L$ lines: coordinates $X\ Y$ of those points. The definition must satisfy every rule from the statement.