CROATIAN OLYMPIAD IN INFORMATICS 2014
Time limit: 1 s
Memory limit: 256 MB
Page \(1/4\)
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, . . . , \(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:
(\(x\)0, y1), (\(x\)1, y1), (\(x\)1, y2), (\(x\)2, y2), (\(x\)2, y3), . . . , (\(x_{N/}\){2}{1}, y{2}), (\(x_{N/}\)}, 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@@RISE_MATH_BLOCK_0@@i > 0 - th\)e height of the histogram is always greater than zero.
5. \(y@@RISE_MATH_BLOCK_1@@i+1 - th\)e 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 formula ^{P}{−}
}_{=0^{y}{(}{)}} ^{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:
diffcount(\(H\)^{′}, H) =
\(W - 1\)
X
\(x=0\)
diff(\(y@@RISE_MATH_BLOCK_2@@1 = y\)2, and 1 else.
abserror(\(H\)^{′}, H) =
\(W - 1\)
X
\(x=0\)
|\(y@@RISE_MATH_BLOCK_3@@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 inaccu-
racy, 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\).
CROATIAN OLYMPIAD IN INFORMATICS 2014
Time limit: 1 s
Memory limit: 256 MB
Page \(2/4\)
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\).

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.
In test cases worth 50 points, it will hold \(G = 1\). In part of those test cases worth 25 points, it
will additionally hold \(M\) ⩽5 000.
In test cases worth 50 points, it will hold \(G = 2\). In part of these test cases worth 25 points, it
will additionally hold \(M\) ⩽5 000.
CROATIAN OLYMPIAD IN INFORMATICS 2014
Time limit: 1 s
Memory limit: 256 MB
Page \(4/4\)

The first line of input contains integers \(N\), \(M\), \(G\) (2 ⩽\(N\) ⩽100 000, 2 ⩽\(M\) ⩽100 000, 1 ⩽\(G\) ⩽
2, N even), respectively: 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 diffcount and 2 for abserror.
Each of the following \(N\) lines contains integers \(X\) and \(Y\) (0 ⩽\(X\) ⩽\(10^{6}\), 1 ⩽\(Y\) ⩽\(10^{6}\)) - coordinates
of one point from the definition of histogram \(H\). The histogram’s definition will comply to all the
conditions from the task statement.
Each of the following \(M\) lines contains integers \(X\) and \(Y\) (0 ⩽\(X\) ⩽\(10^{6}\), 1 ⩽\(Y\) ⩽\(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\).

The first line of output must contain the least possible inaccuracy \(D\). The second line of output
must contain an even integer \(L - th\)e 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 - co\)ordinates of the point
in the histogram’s definition.
The histogram’s definition must comply to 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.
CROATIAN OLYMPIAD IN INFORMATICS 2014
Time limit: 1 s
Memory limit: 256 MB
Page \(3/4\)

생성자가 기록되지 않았습니다.

출처 COCI 2013/2014 Olympiad