ICPC PACNW 2016 F - Illumination

View as PDF

Submit solution

Points: 12
Time limit: 0.6s
Memory limit: 256M

Problem type
Allowed languages
C, C++, Java, Python

You inherited a haunted house. Its floor plan is an n-by-n square grid with l lamps in fixed locations and no interior walls. Each lamp can either illuminate its row or its column, but not both simultaneously. The illumination of each lamp extends by r squares in both directions, so a lamp unobstructed by an exterior wall of the house can illuminate as many as 2r+1 squares.

If a square is illuminated by more than one lamp in its row, or by more than one lamp in its column, the resulting bright spot will scare away ghosts forever, diminishing the value of your property. Is it possible for all lamps to illuminate a row or column, without scaring any ghosts? Note that a square illuminated by two lamps, one in its row and the other in its column, will not scare away the ghosts.


The first line of input contains three positive integers, n, r and l (1 \le n, r, l \le 1000).

Each of the next l lines contains two positive integers r_i and c_i (1 \le r_i, c_i \le n), indicating that there is a lamp in row r_i and column c_i.

It is guaranteed that all lamps are in distinct locations.


Print, on a single line, YES if it is possible to illuminate all lamps as stated above; otherwise, print NO.

Sample Input 1

3 2 5
1 1
1 3
3 1
3 3
2 2

Sample Output 1


Sample Input 2

3 2 6
1 1
1 2
1 3
3 1
3 2
3 3

Sample Output 2

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported


There are no comments at the moment.