COI '13 #2 Histogrami

View as PDF

Submit solution


Points: 30 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

A histogram is a graphical representation of a statistical distribution of data. In other words, it is a function that assigns a positive integer value to each number in the interval 0, 1, 2, \dots, W-1. For this task, we describe a histogram with a series of points in the standard coordinate system which, sequentially, determine the top edge of the area that the histogram encloses.

More specifically, we define a histogram of width W with an even number of points in the form:

\displaystyle (x_0, y_1), (x_1, y_1), (x_1, y_2), (x_2, y_2), (x_2, y_3), \dots, (x_{N/2-1}, y_{N/2}), (x_{N/2}, y_{N/2})

Therefore, starting from the first point, for every pair of adjacent points it must hold that their y coordinates are equal and that their x coordinates are equal. Thus, the histogram begins and ends with a horizontal segment and in between horizontal and vertical segments alternate.

Additionally, the following holds for the shape of a histogram:

  1. x_0 = 0 - the histogram begins on the line x = 0.
  2. x_{N/2} = W - the histogram ends on the line x = W.
  3. x_i < x_{i+1}, for each i = 1, 2, \dots, N/2-1 - the histogram is defined from left to right and the length of each horizontal segment is at least one.
  4. y_i > 0 - the height of the histogram is always greater than zero.
  5. y_i \ne y_{i+1} - the length of each vertical segment is at least one.

For a histogram H, let y_H(x) be the height of the histogram in the interval [x, x+1]. For example, the surface area which the histogram encloses can be calculated by the formula \sum_{x=0}^{W-1} y_H(x). If two histograms, H and H', are given, with equal width W (which can possibly be defined with a different number of points), then we can measure the difference between these two histograms in various ways. This measure of difference between two histograms is also called inaccuracy of histogram H' with regard to histogram H. In this task, we examine two different ways of measuring differences between two histograms and we define them in the following way:

\text{diffcount}(H', H) = \sum_{x=0}^{W-1} \text{diff}(y_H(x), y_{H'}(x)), where \text{diff}(y_1, y_2) = \begin{cases}0 & \text{if }y_1 = y_2 \\ 1 & \text{if }y_1 \ne y_2\end{cases}

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

In other words, the first way measures the number of unit segments [x, x+1] in which the two histograms differ, whereas the second way is the sum of absolute values of differences on those individual unit segments.

Write a program that will, for a given histogram H, set of points S and way of measuring inaccuracy, find and output histogram H' which only uses points from the set S in its definition and has the least possible inaccuracy with regard to the given histogram H.

Figure 1. Illustration of the histogram and the set S in both test cases given below and the solutions for the first and the second way of measuring inaccuracy.

The definition of histogram H' must comply with all aforementioned conditions (for example, there shouldn't be two continuous horizontal segments in the definition of histogram H'), and each point in the definition must be one of the points from the set S.

Input Specification

The first line of input contains integers N, M, G (2 \le N, M \le 10^5, 1 \le G \le 2, N even): the total number of points in the definition of histogram H, number of points in set S and the number which determines what method of measuring the inaccuracy is used: 1 for \text{diffcount} and 2 for \text{abserror}.

Each of the following N lines contains integers X and Y (0 \le X \le 10^6, 1 \le Y \le 10^6) - coordinates of one point from the definition of histogram H. The histogram's definition will comply with all the conditions from the task statement.

Each of the following M lines contains integers X and Y (0 \le X \le 10^6, 1 \le Y \le 10^6) - coordinates of one point from set S. All the points in the set S will be different from one another, but they can match with points from the definition of the histogram H.

Output Specification

The first line of output must contain the least possible inaccuracy D.

The second line of output must contain an even integer L - the total number of points in the definition of the required optimal histogram.

In each of the following L lines, output two integers X and Y - coordinates of the point in the histogram's definition.

The histogram's definition must comply with all the conditions from the task.

Please note: The solution may not be unique, but the input data will be such that there is always at least one solution.

Constraints

SubtaskPointsConstraints
125G = 1, M \le 5\,000
225G = 1
325G = 2, M \le 5\,000
425G = 2

Scoring

If the histogram's definition is incorrect or wasn't output, but the first line of output is correct (minimal inaccuracy), your solution will get 70\% of total points for that test case.

Sample Input 1

10 12 1
0 2
2 2
2 3
4 3
4 1
5 1
5 5
9 5
9 2
10 2
0 4
0 6
3 3
3 6
9 4
9 1
5 3
5 5
10 5
9 2
10 1
8 5

Sample Output 1

5
6
0 6
3 6
3 3
5 3
5 5
10 5

Sample Input 2

10 12 2
0 2
2 2
2 3
4 3
4 1
5 1
5 5
9 5
9 2
10 2
0 4
0 6
3 3
3 6
9 4
9 1
5 3
5 5
10 5
9 2
10 1
8 5

Sample Output 2

14
4
0 4
9 4
9 1
10 1

Comments

There are no comments at the moment.