from collections import defaultdict, deque
UD = 0 # Up-Down, lamp is vertical
LR = 1 # Left-Right, lamp is horizontal
n, r, k = map(int,input().split())
idxToPt = defaultdict(tuple)
for i in range(k):
ptX, ptY = map(int, input().split())
idxToPt[i + 1] = (ptX, ptY)
g1 = {i: [] for i in range(1, k + 1)}
g2 = {i: [] for i in range(1, k + 1)}
for i in range(1, k + 1):
for j in range(i + 1, k + 1):
x1, y1 = idxToPt[i]
x2, y2 = idxToPt[j]
# same x coordinate: check y coordinate for UD conflict
if x1 == x2:
if abs(y1 - y2) <= 2 * r:
g1[i].append(j)
g1[j].append(i)
if y1 == y2: # same y coordinate: check x coordinate for LR conflict
if abs(x1 - x2) <= 2 * r:
g2[i].append(j)
g2[j].append(i)
def bfs(start):
color[start] = 0
q = deque([start])
while q:
current = q.popleft()
# assert color[current] != -1 # will cause runtime error if false
if color[current] == UD:
for neighbor in g1[current]:
if color[neighbor] == -1:
color[neighbor] = LR # 1 - color[current] also works
q.append(neighbor)
elif color[neighbor] == UD: # can't have both UD in graph
return False
else: # color[current] is 1
for neighbor in g2[current]:
if color[neighbor] == -1:
color[neighbor] = UD
q.append(neighbor)
elif color[neighbor] == LR: # can't have both LR in graph 2
# print(current, neighbor)
return False
return True
color = [-1] * (k + 1)
for i in range(1, k + 1):
if color[i] == -1:
res = bfs(i)
if not res:
# print(color)
print(0)
exit()
print(1)
This looks to me like a standard 2-SAT problem. Every lamp has to be either horizontal or vertical, if one lamp is horizontal then some other lamps in the same row must be vertical and vice versa. If you worry about TLE then you could do the full binary tree trick (1903F - Babysitting).