Dịch bệnh

Xem PDF

Nộp bài


Điểm: 15 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 512M

Tác giả:
Dạng bài

Thành phố Bytecity có \(N\) cư dân được đánh số từ \(1\) đến \(N\). Bản đồ của thành phố được mô phỏng trên hệ trục tọa độ \(\text{Oxy}\). Cư dân \(i\) sinh sống ở tọa độ \(\left(X_i, Y_i\right)\).

Cư dân \(1\) vừa bị nhiễm một loại virus lạ. Đặc điểm của loại virus này là sẽ nhanh chóng phát tán cho tất cả các cư dân nằm trong bán kính \(D\) tính từ vị trí của người nhiễm bệnh. Giả định tất cả các cư dân đều không di chuyển trong quá trình lây nhiễm, bạn hãy viết chương trình xác định xem những cư dân nào sẽ bị nhiễm virus ở trạng thái sau cùng nhé!

Input
  • Dòng đầu chứa hai số nguyên dương \(N\) và \(D\) \(\left(1\le N, D\le 2000\right)\).
  • Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(X_i\) và \(Y_i\) \(\left(-1000\le X_i, Y_i\le 1000\right)\). Dữ liệu đảm bảo \(\left(X_i, Y_i\right)\ne \left(X_j, Y_j\right)\) với mọi \(i\ne j\).
Output
  • In ra \(N\) dòng, dòng thứ \(i\) chứa xâu Yes nếu cư dân \(i\) sẽ bị nhiễm virus trong trạng thái sau cùng và chứa xâu No trong trường hợp ngược lại.
Ví dụ
Sample input 01
4 5
2 -1
3 1
8 8
0 5
Sample output 01
Yes
Yes
No
Yes
Giải thích
  • Cư dân \(2\) sẽ bị nhiễm virus vì khoảng cách giữa cư dân \(2\) và cư dân \(1\) là \(\sqrt{5}\).
  • Cư dân \(4\) cũng sẽ bị nhiễm virus vì khoảng cách giữa cư dân \(4\) và cư dân \(2\) là \(5\).
  • Cư dân \(3\) không bị nhiễm virus vì khoảng cách từ mọi cư dân bị nhiễm đến cư dân \(3\) đều lớn hơn \(5\).
Sample input 02
3 1
0 0
-1000 -1000
1000 1000
Sample output 02
Yes
No
No
Sample input 03
9 4
3 2
6 -1
1 6
6 5
-2 -3
5 3
2 -3
2 1
2 6
Sample output 03
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No