Xét bàn cờ tổng
quát kích thước kx
k, các hàng của
bàn cờ được đánh số từ 1 tới k từ trên xuống dưới và các cột của
bàn cờ được đánh số từ 1 tới k từ trái qua phải. Ô nằm trên giao của hàng i
và cột j được gọi là ô (i, j). Từ bàn cờ ban đầu gồm các ô
trống, người ta đặt đúng n quân hậu vào n ô hoàn toàn phân biệt
trên bàn cờ.
Ta nói một quân
hậu ở ô (x, y) khống chế được ô trống (x’, y’) nếu
đoạn thẳng nối tâm hai ô đó song song với một trong hai cạnh bàn cờ hoặc song
song với một trong hai đường chéo của bàn cờ, đồng thời đoạn thẳng nối tâm của
hai ô (x, y) và (x’ , y’) không đi qua
tâm của bất kỳ ô nào chứa quân hậu khác.
Như ví dụ trên,
quân hậu ở ô (4, 4) có thể khống chế được 16 ô trống đánh dấu “ü” trong hình.
Yêu cầu: Cho biết kích thước bàn cờ và vị
trí n
quân hậu, hãy đếm số ô trống bị quân
hậu khống chế.
Dữ liệu: Vào từ file văn bản QUEENS.INP
·
Dòng 1 chứa hai số nguyên dương k≤109,
n≤105
·
n dòng tiếp theo, dòng thứ i chứa hai số
nguyên dương lần lượt là chỉ số hàng và chỉ số cột của quân hậu thứ i
Kết quả: Ghi ra file
văn bản QUEENS.OUT n dòng, dòng thứ
i ghi số ô trống
bị quân hậu thứ i khống chế.
Ví dụ:
