PIZZALOC - Pizza Location

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/pizzaloc

Picko muốn mở một số cửa hàng pizza tại 1 số địa điểm. Bánh pizza sẽ cung cấp cho mọi khách hàng nằm trong hình tròn bán kính R với tâm là các địa điểm được chọn.

Xác định số khách hàng lớn nhất có thể phục vụ.

Input

Dòng đầu là hai số K, R : số nhà hàng có thể được mở và bán kính phục vụ của mỗi nhà hàng,1 ≤ K ≤ 10, 1 ≤ R ≤ 500.

Dòng thứ hai là M, số địa điểm có thể đặt nhà hàng, K ≤ M ≤ 20.

M dòng tiếp theo, mỗi dòng là 2 số nguyên X và Y, -1000 ≤ X,Y ≤ 1000.

Dòng tiếp theo là N, số khu nhà, 1 ≤ N ≤ 100.

Mỗi dòng trong N dòng tiếp theo là 3 số nguyên X, Y , S, là tọa độ và số người ở khu nhà đó, -1000 ≤ X,Y ≤ 1000, 1 ≤ S ≤ 100.

Khu nhà nằm trong bán kính của nhà hàng nếu khoảng cách giữa chúng <= R. Không có 2 khu nhà tại cùng 1 địa điểm.

Output

Ghi ra số người tối đa có thể được phục vụ.

Sample

pizza.in 
2 2 
3 
1 0 
4 0 
7 0 
4 
0 0 1 
3 0 7 
5 0 9 
8 0 1 
 
pizza.out 
18 

pizza.in 
2 2 
3 
-2 0 
0 1 
3 0 
8 
-3 1 1 
-3 0 1 
-3 -1 1 
-2 -1 1 
0 0 3 
0 2 1 
2 1 3 
4 0 2 
 
pizza.out 
12 

pizza.in 
3 3 
5 
0 0 
1 6 
2 3 
6 6 
7 2 
8 
0 1 2 
0 5 3 
0 6 1 
1 0 1 
3 2 3 
3 6 2 
6 2 4 
8 6 3 
 
pizza.out 
17 


Được gửi lên bởi:psetter
Ngày:2009-04-08
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED
Nguồn bài:COI 03

hide comments
2021-05-27 18:03:00
Tham khảo: https://vnspoj.github.io/problems/PIZZALOC
2020-02-24 04:27:53
cay quá khai báo mảng thiếu phần tử nên bị WA :(
2019-09-26 03:38:13
Xin chào các fan hâm mộ.
duonght_pro_xinhgainhathemattroi_:)
2019-08-12 12:19:19
tự tin 1 đấm AC :))
2019-03-14 09:02:35
https://youtu.be/G2HVHCiAYMI
say oh yeah
2018-12-25 04:27:09
Thử dùng bitset khởi tạo trước xem mỗi nhà hàng phục vụ được khác hàng nào thì AC :v
CYB
2016-11-27 02:32:07
Đệ Quy + BIT -> AC
sub chục lần đủ các kiểu mới AC
2016-11-03 15:40:06
Bài này áp dụng backtrack. Tuy nhiên, có một chú ý là mình lưu lại những ngôi nhà mà tại mỗi vị trí, nhà hàng có thể phục vụ vào một mảng => sẽ không bị time limit.
http://thuattoan.phamvanlam.com/spoj-com-thuat-toan-bai-pizzaloc-pizza-location/
2016-07-12 10:52:46
long long=TLE
int=AC????
2016-06-19 18:16:04 trần thị quỳnh châu
Bài này đặt cận thế nào hả mọi người. Em bị quá thời gian
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.