framework: www.github.com/chu-mirror/probs

@[main@]
{ int w;
	while (scanf("%d", &w), w != 0) {
		printf("%d\n", w);
		@{handle image of width |w|@}
	}
	printf("0\n");
}
@

Each pair is labeled with a position, for example, for a image of width 5:
	XXXXX
	XXXXX
	XX
the next pair read in is (5, 0):
	XXXXX
	XXXXX
	XX000
	00
then, that pair is labeled to (12, 5, 0), 12 is the position of first pixel of the pair in whole image.

Each loop reads in one pair, compute output, then cut off useless information.  The useless information,
for example, the first row of above example is useless for later processing, the output based on this row
can be computed in this stage.

The information is reserved in a buffer, the order of pairs is relevent, left to right, old to new.

@[data@]
int buffer[1000][3];
int buffer_size;
@

@[functions@]
void push_pair(int p, int l, int v)
{
	if (l == 0) return;
	buffer[buffer_size][0] = p;
	buffer[buffer_size][1] = l;
	buffer[buffer_size][2] = v;
	buffer_size++;
}

int buffer_rows(int w)
{ int i, np; /* number of pixels */
	for (np = 0, i = 0; i < buffer_size; i++) {
		np += buffer[i][1];
	}
	return np/w;
}
@

Pair (p, l, v) can be divided to (p, l0, v) and (p+l0, l-l0, v) without lossing of information.
This feature can be used to align pairs.  I want the pairs in buffer to satify:
1. p+l <= (floor(p/w)+1)*w
2. if not 1, p%w = 0, (p+l)%w == 0

@[functions@]
void push_aligned(int p, int l, int v, int w)
{
	if (p+l <= (p/w + 1)*w) {
		push_pair(p, l, v);
	} else {
		if (p%w == 0) {
			push_pair(p, l-(l%w), v);
			push_pair(p+l-(l%w), l%w, v);
		} else {
			push_pair(p, (p/w+1)*w-p, v);
			push_aligned((p/w+1)*w, l+p-(p/w+1)*w, v, w);
		}
	}
}
@

The algorithm is based on influence's calculating, assume that we have continuous three rows of pixels:
	XXXXX
	YYYYY
	ZZZZZ
then, the rows "YYYYY"'s corresponding output is completely influenced by these three rows.
In every loop, we assvme that the influence X to Y has been computed and saved, we compute the influence
Y to Y, Y to Z, and Z to Y, then go to next loop.

The computation of influence is done on pairs directly, we need to develop a new language for this purpose.
Let's say, segments.  A segment is a tuple (l, r), we can define that:
	intersect(s1, s2) = (max(l1, l2), min(r1, r2))
influence is usually computed based on intersection of two segments.

@[functions@]
int max2(int a, int b) { return a>b ? a : b; }
int min2(int a, int b) { return a<b ? a : b; }
void intersection(int l1, int r1, int l2, int r2, int *l, int *r)
{
	*l = max2(l1, l2), *r = min2(r1, r2);
}
@

If pair do influence is of (p1, l1, v1), pair influenced is of (p2, l2, v2),
	X	X	X	X	X
		p1	p1+1
	Y	Y	Y	Y	Y
	p2		p2+2
then the intersection is from (p1-1+w, p1+l1+1+w) and (p2, p2+l2), in this example (p1+4, p2+2).

And two influences (p1, l1, v1), (p2, l2, v2), if they have intersection, the accumulative influence
is their union, and set the intersection part's value to max(v1, v2).

The computed influence is recorded first in a buffer, in sequence.
@[data@]
int influence[1000][3];
int influence_size;
@

@[functions@]
void queue_influence(int p, int l, int v)
{ int end = influence_size - 1;
	if (l == 0) return;
	if (influence_size && influence[end][2] == v) {
		influence[end][1] += l;
		return;
	}
	influence[influence_size][0] = p;
	influence[influence_size][1] = l;
	influence[influence_size][2] = v;
	influence_size++;
}

void append_influence(int p, int l, int v)
{ int i; int backup[1000][3], backup_size;
	memcpy(backup, influence, influence_size * sizeof(influence[0]));
	backup_size = influence_size;
	influence_size = 0;
	for (i = 0; i < backup_size; i++) { int il, ir;
		@{compute accumulation of |influence[i]| and intersection with |(p, l, v)|, and substract that intersection@}
	}
	queue_influence(p, l, v);
}
@

@[compute accumulation of |influence[i]| and intersection with |(p, l, v)|, and substract that intersection@]
{
	intersection(backup[i][0], backup[i][0]+backup[i][1],
		     p, p+l, &il, &ir);
	if (il < ir) {
		if (backup[i][0] < il) {
			queue_influence(backup[i][0], il-backup[i][0], backup[i][2]);
			backup[i][1] = backup[i][1]-il+backup[i][0];
			backup[i][0] = il;
		}
		queue_influence(il, ir-il, max2(v, backup[i][2]));
		p += ir-il;
		l -= ir-il;
		backup[i][0] += ir-il;
		backup[i][1] -= ir-il;
	}
	queue_influence(backup[i][0], backup[i][1], backup[i][2]);
}
@

This is the main loop of image processing, every loop is invariant at: the first line has
accepted influence from previous line, the second line does not yet take part in computing yet.

@[handle image of width |w|@]
{ int p = 0; int l, v;
	@{initialize@}
	while (scanf("%d%d", &v, &l), l != 0 || v != 0) {
		push_aligned(p, l, v, w); p+=l;
		@{maintain@}
		@{move appropriate number of influence to output queue@} /* mainly for efficiency consideration */
	}
	@{clean@}
	@{print influence@}
	printf("0 0\n");
}
@

The first line does not have a previous line influencing it.
@[initialize@]
queue_influence(0, w, 0);
@

Based on the type of pair and the status of _buffer_, there's three kinds of maintaining.
1. the first pair in _buffer_ contains multiple lines
2. the first pair in _buffer_ contains pixels in one line
3. there is only one line in _buffer_ now

@[maintain@]
{ int nr; /* number of rows */
	nr = buffer_rows(w);
	while (nr > 1) {
		if (buffer[0][1] > w) {
			@{handle multiple lines pair@}
		} else {
			@{handle single line pair@}
		}
		nr = buffer_rows(w);
	}
}
@

The second row does not contribute influence, and might add a chunk of influence of 0
if the total number of rows is bigger than 2.
@[handle multiple lines pair@]
{
	queue_influence(buffer[0][0]+w, buffer[0][1]-w, 0);
	buffer[0][0] = buffer[0][0]+buffer[0][1]-w;
	buffer[0][1] = w;
}
@

@[handle single line pair@]
{ int i; int np; /* the next position in buffer where line starts */
	for (i = 1; i < buffer_size; i++) {
		if (buffer[i][0] % w == 0) {
			np = i;
			break;
		}
	}
	@{compute influence caused by second line on first line@}
	@{compute influence caused by first line on first line@}
	@{compute influence caused by first line on second line@}
	@{delete first line from |buffer|@}
}
@

@[delete first line from |buffer|@]
{ int end = buffer_size-1, i;
	buffer_size = 0;
	for (i = np; i <= end; i++) {
		push_pair(buffer[i][0], buffer[i][1], buffer[i][2]);
	}
}
@

Three types of causing of influence.
@[compute influence caused by second line on first line@]
{ int lp, i, j; /* length processed */
	for (lp = 0, i = np; lp < w; lp += buffer[i][1], i++) {
		for (j = 0; j < np; j++) { int l, r;
			intersection(buffer[i][0]-1-w, buffer[i][0]+buffer[i][1]+1-w,
			             buffer[j][0], buffer[j][0]+buffer[j][1], &l, &r);
			if (l < r) {
				append_influence(l, r-l, abs(buffer[i][2]-buffer[j][2]));
			}
		}
	}
}
@

@[compute influence caused by first line on first line@]
{ int i;
	for (i = 0; i < np-1; i++) {
		append_influence(buffer[i][0]+buffer[i][1], 1, abs(buffer[i][2]-buffer[i+1][2]));
	}
	for (i = 1; i < np; i++) {
		append_influence(buffer[i][0]-1, 1, abs(buffer[i][2]-buffer[i-1][2]));
	}
}
@

@[compute influence caused by first line on second line@]
{ int lp, i, j;
	for (i = 0; i < np; i++) {
		for (lp = 0, j = np; lp < w; lp += buffer[j][1], j++) { int l, r;
			intersection(buffer[i][0]-1+w, buffer[i][0]+buffer[i][1]+1+w,
			             buffer[j][0], buffer[j][0]+buffer[j][1], &l, &r);
			r = min2(r, (l/w+1)*w); /* if the second line is multiple line pair */
			if (l < r) {
				append_influence(l, r-l, abs(buffer[i][2]-buffer[j][2]));
			}
		}
	}
}
@

I use another buffer in queuing output.
@[data@]
int output_queue[3000][3];
int output_queue_size;
@

@[functions@]
void queue_output(int p, int l, int v)
{ int end = output_queue_size - 1;
	fixed_point = output_queue[end][0] + output_queue[end][1] == p;
	if (l == 0) return;
	if (output_queue_size && output_queue[end][2] == v) {
		output_queue[end][1] += l;
		return;
	}
	output_queue[output_queue_size][0] = p;
	output_queue[output_queue_size][1] = l;
	output_queue[output_queue_size][2] = v;
	output_queue_size++;
}
@

After maintaining, there's one row of influence still waiting for accumulating.
@[move appropriate number of influence to output queue@]
{ int end, i, np;
	for (np = 0, end = influence_size; end && np < w; end--) {
		np += influence[end-1][1];
	}
	for (i = 0; i < end; i++) {
		queue_output(influence[i][0], influence[i][1], influence[i][2]);
	}
	for (i = end; i < influence_size; i++) {
		influence[i-end][0] = influence[i][0];
		influence[i-end][1] = influence[i][1];
		influence[i-end][2] = influence[i][2];
	}
	influence_size -= end;
}
@

There is one row left.
@[clean@]
{ int i;
	for (i = 0; i < buffer_size-1; i++) {
		append_influence(buffer[i][0]+buffer[i][1], 1, abs(buffer[i][2]-buffer[i+1][2]));
	}
	for (i = 1; i < buffer_size; i++) {
		append_influence(buffer[i][0]-1, 1, abs(buffer[i][2]-buffer[i-1][2]));
	}
	buffer_size = 0;
	for (i = 0; i < influence_size; i++) {
		queue_output(influence[i][0], influence[i][1], influence[i][2]);
	}
	influence_size = 0;
}
@

@[print influence@]
{ int i;
	for (i = 0; i < output_queue_size; i++) {
		printf("%d %d\n", output_queue[i][2], output_queue[i][1]);
	}
	output_queue_size = 0;
}
@

@[samples@]
===
7
15 4
100 15
25 2
175 2
25 5
175 2
25 5
0 0
0
>>>
7
85 5
0 2
85 5
75 10
150 2
75 3
0 2
150 2
0 4
0 0
0
===
10
35 500000000
200 500000000
0 0
0
>>>
10
0 499999990
165 20
0 499999990
0 0
0
===
3
255 1
10 1
255 2
10 1
255 2
10 1
255 1
0 0
0
>>>
3
245 9
0 0
0
===
5
21818 1
6255 2
28702 3
25687 4
14411 5
836 6
970 7
31763 8
2842 9
1555 10
0 0
0
>>>
5
15563 1
22447 3
3015 1
22447 1
19432 3
11276 1
14291 2
13575 8
134 2
30793 12
28921 8
1287 8
0 5
0 0
0
===
5
1 1
2 1
3 1
4 1
5 1
0 0
0
>>>
5
1 5
0 0
0
@