题解 P4335 【[COCI2007] Sabor】

· · 题解

搬运+翻译Croatian Olympiad in Informatics 2007官方题解

Upon closer inspection, the task asks to count, among all cells at most K steps from the origin, thenumber of cells with even distance and the number of cells with odd distance.

这道题要求我们计数，到原点的距离不超过K步的格子中，具有偶数距离和奇数距离的格子数。

One might say that we'recolouring the cells with two colours.Thecolour of a cell is uniquely determined by its coordinates, since each step changes the parity of theexpression x+y. Because of this, two adjacent cells are necessarily coloured differently. Additionally, thedistances of two adjacent cells differ by exactly 1.

有人说可以用二分图染色乱搞一下。单元格的颜色是由它的坐标决定的，因为每走一步都会改变x+y的奇偶性。因此相邻的两个格子颜色一定不同。此外，两个相邻格子的距离是1。

The image shows the second sample test, with a slightly larger number of steps S. Observe the smallestrectangle surrounding all obstacles and the origin, and expand it one cell in all four directions:

图片显示了第二组样例，这组样例的S比较大。观察包含所有障碍物和原点的最小矩形，在其基础上扩展一圈。

The absolute values of the obstacles' coordinates are at most 1000 so the distances of all cells inside therectangle can be found with breadth-first search.

面向数据编程，障碍物坐标的绝对值最多为1000，所以这个矩形内所有的格子都可以BFS到。

For example, consider a cell is on the left edge of the rectangle (but inside it), distance some D stepsfrom the origin. Then exactly K–D cells to its left (outside the rectangle) will be coloured, and simpleformulas will give the number of cells of one and the other colour in O(1). We proceed identically forcells on the other three edges of the rectangle.

例如，考虑一个在这个矩形左边缘上（但是在其内部）的一个格子，距离原点D步。那么在它左边所有离原点K~D步的格子都可以在O(1)时间内染上色。我们对其他三边也这么搞。

We still need to count the cells off the corners; for example, the cells above and to the left of the yellowcell in the upper-left corner of the rectangle. A triangular pattern is obvious and there are formulas (seesample code) for this case too. But since S is on the order of millions, doing it in O(S) for each cornerinstead of O(1) will do, too.

我们还要计算角落里的格子，比如左上边的几个格。一个三角形是很容易用公式（你可以看标程里的公式）算的。但因为S是1e6的，所以每个角O(S)而不是O(1)也可过。

/*
  Croatian Olympiad in Informatics 2007
  Task SABOR
*/

#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;

#define MAX 1000

void edge(int x, int y, int d, int K, long long res[2])
{
   res[(x+y)%2]   += (K-d)/2;
   res[(x+y+1)%2] += (K-d+1)/2;
}

void corner(int x, int y, int d, int K, long long res[2])
{
   long long n;
   n = (K-d)/2;   res[(x+y)%2]   += n*n;
   n = (K-d-1)/2; res[(x+y+1)%2] += n*(n+1);
}

int main()
{
   int P, K;
   scanf( "%d%d", &P, &K );
   ++K;

   static int d[2*MAX+3][2*MAX+3];
   int x0=MAX+1, y0=MAX+1;
   int
      minx = x0, maxx = x0,
      miny = y0, maxy = y0;

   for ( int i=0; i<P; ++i ) {
      int x, y;
      scanf( "%d%d", &x, &y );
      x += x0; y += y0;
      minx = min( minx, x ); maxx = max( maxx, x );
      miny = min( miny, y ); maxy = max( maxy, y );
      d[x][y] = -1;
   }
   --minx; --miny;
   ++maxx; ++maxy;

   long long res[2] = { 0, 0 };

   queue<int> qx, qy;
   d[x0][y0] = 1;
   qx.push(x0); qy.push(y0); 
   while ( !qx.empty() ) {
      int x = qx.front(); qx.pop();
      int y = qy.front(); qy.pop();

      ++res[(x+y)%2];
      if ( d[x][y] == K ) {
         continue;
      }
      if ( x == minx || x == maxx ) edge(x, y, d[x][y], K, res);
      if ( y == miny || y == maxy ) edge(x, y, d[x][y], K, res);

      static const int dx[] = { -1, 0, 1, 0 };
      static const int dy[] = { 0, 1, 0, -1 };
      for ( int dir=0; dir<4; ++dir ) {
         int nx = x + dx[dir], ny = y + dy[dir];
         if ( nx < minx || nx > maxx || ny < miny || ny > maxy || d[nx][ny] != 0 ) continue;

         d[nx][ny] = d[x][y] + 1;
         qx.push( nx ); qy.push( ny );
      }
   }

   if ( d[minx][miny] > 0 ) corner( minx, miny, d[minx][miny], K, res );
   if ( d[minx][maxy] > 0 ) corner( minx, maxy, d[minx][maxy], K, res );
   if ( d[maxx][miny] > 0 ) corner( maxx, miny, d[maxx][miny], K, res );
   if ( d[maxx][maxy] > 0 ) corner( maxx, maxy, d[maxx][maxy], K, res );

   cout << res[0] << ' ' << res[1] << endl;

   return 0;
}