SRM 546 Div2 Medium TwoRectangles

問題

2つの長方形が与えられる.両者がどのようにして交わるのかを以下のように返す.

  • 面積が0でない領域を共有する,"rectangle"を返す
  • 辺を共有する, "segment"を返す
  • 点を共有する, "point"を返す
  • それ以外, "none"を返す

解答

長方形が表す領域をboolで表す.
2つの長方形をA, Bとすると

  • A[i][j] = B[i][j] = trueならば面積を共有する(条件1)
  • A[i][j] = B[i+i2][j+j2] = trueならば辺を共有する((i2, j2) \in {(-1, 0), (0, 1), (1, 0), (0, -1)})(条件2)
  • A[i][j] = B[i+i2][j+j2] = trueならば点を共有する(-1 <= i2, j2 <= 1)(条件3)

となる.上の条件を満たすかどうかチェックする.

解説では2次元のintersectionが1次元に落とし込めることを解説していて面白い.
Login - TopCoder Wiki

class TwoRectangles
{
public:
  string describeIntersection(vector <int> A, vector <int> B)
    {
      int W = 1004;
      vector<vector<bool> > M2(W, vector<bool>(W, false));
      int i, j;
      int dx[4] = {-1, 0, 1, 0};
      int dy[4] = {0, -1, 0, 1};
      int rectangle = 1 << 3;
      int segment = 1 << 2;
      int point = 1 << 1;
      for(i = B[0]; i < B[2]; i++){
        for(j = B[1]; j < B[3]; j++){
          M2[i+1][j+1] = true;
        }
      }
      int flag = 0;
      for(i = A[0]; i < A[2]; i++){
        for(j = A[1]; j < A[3]; j++){
          int x = i+1;
          int y = j+1;
          if (M2[x][y]) flag |= rectangle;
          for(int k = 0; k < 4; k++){
            if (M2[x+dx[k]][y+dy[k]]) flag |= segment;
          }
          for(int i2 = -1; i2 <= 1; i2++){
            for(int j2 = -1; j2 <= 1; j2++){
              if(M2[x+i2][y+j2]) flag |= point;
            }
          }
        }
      }
      if(flag & rectangle) return "rectangle";
      if(flag & segment) return "segment";
      if(flag & point) return "point";
      return "none";
    }
};