POJ 1009 Edge Detection

Description

IONU Satellite Imaging, Inc. records and stores very large images using run length encoding. You are to write a program that reads a compressed image, finds the edges in the image, as described below, and outputs another compressed image of the detected edges. 

A simple edge detection algorithm sets an output pixel's value to be the maximum absolute value of the differences between it and all its surrounding pixels in the input image. Consider the input image below: 

The upper left pixel in the output image is the maximum of the values |15-15|,|15-100|, and |15-100|, which is 85. The pixel in the 4th row, 2nd column is computed as the maximum of |175-100|, |175-100|, |175-100|, |175-175|, |175-25|, |175-175|,|175-175|, and |175-25|, which is 150. 

Images contain 2 to 1,000,000,000 (10 

9) pixels. All images are encoded using run length encoding (RLE). This is a sequence of pairs, containing pixel value (0-255) and run length (1-10 

9). Input images have at most 1,000 of these pairs. Successive pairs have different pixel values. All lines in an image contain the same number of pixels. 

Input

Input consists of information for one or more images. Each image starts with the width, in pixels, of each image line. This is followed by the RLE pairs, one pair per line. A line with 0 0 indicates the end of the data for that image. An image width of 0 indicates there are no more images to process. The first image in the example input encodes the 5x7 input image above. 

Output

Output is a series of edge-detected images, in the same format as the input images, except that there may be more than 1,000 RLE pairs. 

Sample Input

715 4
100 15
25 2
175 2
25 5
175 2
25 5
0 0
10
35 500000000
200 500000000
0 0
3
255 1
10 1
255 2
10 1
255 2
10 1
255 1
0 0
0      

Sample Output

785 5
0 2
85 5
75 10
150 2
75 3
0 2
150 2
0 4
0 0
10
0 499999990
165 20
0 499999990
0 0
3
245 9
0 0
0      

Hint

A brute force solution that attempts to compute an output value for every individual pixel will likely fail due to space or time constraints. 

是一道經典好題，很難想到完美的做法，看了好幾個人的題解，并且搞了好幾組測試資料才算搞定。

證明方法就略了（因為不知道，哈哈哈），隻要考慮給出的每個連續段的首尾，這個改變一定會影響周圍的八個點。

于是就把這9個點重新算一遍即可，然後排序，相同區間合并即可。

需要注意的是邊界上的點，容易出現錯誤，是以算9個點的時候，直接加減，不是超過整個圖的就重算。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define fi first
#define se second
#define mp(i,j) make_pair(i,j)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 9973;
const int N = 3e5 + 10;
int n, x[N], y[N], t, sz;
pii ans[N];

int find(int z)
{
  return x[lower_bound(y + 1, y + t, z) - y];
}

void add(int x)
{
  if (x<1 || x>y[t - 1]) return;
  int q = 0, z = find(x);
  if (x > n)
  {
    if ((x - 1) % n) q = max(q, abs(find(x - n - 1) - z));
    q = max(q, abs(find(x - n) - z));
    if (x % n) q = max(q, abs(find(x - n + 1) - z));
  }
  if ((x - 1) % n) q = max(q, abs(find(x - 1) - z));
  if (x % n) q = max(q, abs(find(x + 1) - z));
  if (x <= y[t - 1] - n)
  {
    if ((x - 1) % n) q = max(q, abs(find(x + n - 1) - z));
    q = max(q, abs(find(x + n) - z));
    if (x % n) q = max(q, abs(find(x + n + 1) - z));
  }
  ans[sz++] = mp(x, q);
}

void get(int x)
{
  rep(i, -1, 1) rep(j, -1, 1) add(x + i * n + j);
}

bool cmp(const pii&a, const pii&b)
{
  return a.first < b.first;
}

int main()
{
  while (scanf("%d", &n), n)
  {
    t = 1; y[0] = sz = 0;
    while (scanf("%d%d", &x[t], &y[t]))
    {
      if (x[t] + y[t] == 0) break;
      y[t] += y[t - 1]; t++;
    }
    rep(i, 1, t - 1) get(y[i - 1] + 1), get(y[i]);
    sort(ans, ans + sz, cmp);
    ans[sz] = mp(y[t - 1] + 1, -1);
    printf("%d\n", n);
    for (int i = 0, j = 0; i < sz; i = j)
    {
      for (; j < sz&&ans[i].se == ans[j].se; j++);
      printf("%d %d\n", ans[i].se, ans[j].fi - ans[i].fi);
    }
    printf("0 0\n");
  }
  printf("0\n");
  return 0;
}