マス \((P,Q)\) を中心とするX字によりマス \((X,Y)\) が黒く塗られるための必要十分条件は \(P+Q=X+Y\) または \(P-Q=X-Y\) となることです。

よって、集合 \(\{P_1+Q_1,\ldots,P_N+Q_N\}\) 及び \(\{P_1-Q_1,\ldots,P_N-Q_N\}\) を保持することで、各マス \((X,Y)\) が黒く塗られるかどうかを \(O(\log N)\) で判定することができます。

実装例(Python)

N,A,B,C,D = map(int,input().split())
wa=set()
sa=set()

for _ in range(N):
  P,Q = map(int,input().split())
  wa.add(P+Q)
  sa.add(P-Q)

for i in range(A,B+1):
  for j in range(C,D+1):
    if (i+j in wa) or (i-j in sa):
      print("#", end="")
    else:
      print(".", end="")
  print()