uva 1526 - Edge Detection（二分+排序）

題目鏈接：uva 1526 - Edge Detection

題目大意：先給出width，表示說一個w*w的圖片，每個位置上的數值代表該位置的像素，現在有一種算法用於裝換圖片，轉換後圖片的表示方式為，每個位置上的數值為原先圖上位置的像素與周圍8個位置像素之差的絕對值的最大值。

然後圖的表示給出和要求輸出方式為run length encoding，即由若干對兩位數組成，分別表示像素和連續個數。給出原圖的RLE，輸出轉換後的RLE。

解題思路：首先會受到影響的肯定為交界處，所以找出所有的交界處，將周圍8個數取出單獨考慮，在查找值時用二分。

#include 
#include 
#include 
#include 

using namespace std;
const int N = 1005;

int inN, outN, inData[N][2];
int width, total;
struct state {
	int val, pos;
}outData[N*9];

void init () {
	total = inN = outN = 0;
	
	memset(inData, 0, sizeof(inData));
	int a, b;
	while (scanf("%d%d", &a, &b) == 2) {
		inData[inN][0] = a;
		inData[inN][1] = total;
		total += b;
		if (0 == b) break;
		++inN;
	}
}

int getValue (int pos) {
	int l = 0, r = inN - 1;

	while (l <= r) {
		int mid = (l + r) / 2;
		if (inData[mid][1] <= pos)
			l = mid + 1;
		else
			r = mid - 1;
	}
	return inData[r][0];
}

int cal(int pos) {
	int r = pos / width;
	int l = pos % width;

	int ans = 0;
	for (int i = r - 1; i <= r + 1; i++) {
		for (int j = l - 1; j <= l + 1; j++) {
			int p = i * width + j;
			if (i < 0 || j < 0 || j >= width || p >= total || p == pos)
				continue;
			int t = abs(getValue(p) - getValue(pos));
			ans = max(ans, t);
		}
	}
	return ans;
}

inline bool cmp (const state& a, const state& b) {
	return a.pos < b.pos;
}

void solve () {
	for (int i = 0; i <= inN; i++) {
		int r = inData[i][1] / width;
		int l = inData[i][1] % width;

		for (int j = r - 1; j <= r + 1; j++) {
			for (int k = l - 1; k <= l + 1; k++) {
				int p = j * width + k;
				if (j < 0 || k < 0 || p >= total || p < 0)
					continue;
				outData[outN].val = cal(p);
				outData[outN].pos = p;
				++outN;
			}
		}
	}

	sort (outData, outData + outN, cmp);
	state cur = outData[0];
	for (int i = 0; i < outN; i++) {
		if (cur.val == outData[i].val) continue;

		printf("%d %d\n", cur.val, outData[i].pos - cur.pos);
		cur = outData[i];
	}
	printf("%d %d\n", cur.val, total - cur.pos);
	printf("0 0\n");
}

int main () {
	while (scanf("%d", &width) == 1 && width) {
		init ();
		printf("%d\n", width);
		solve ();
	}
	printf("0\n");
	return 0;
}