VPHSTAR - Ngắm sao
Giới hạn- Thời gian: 3.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274862/problem/V
Chíp có sở thích ngắm sao vào mỗi buổi đêm. Đêm nay, trời đặc biệt đầy sao. Chíp đếm được có N ngôi sao trên trời, Chíp ghi nhớ mỗi ngôi sao và đánh số chúng từ 1 đến N . Mỗi ngôi sao được biểu diễn bằng một đường tròn trên mặt phẳng tọa độ, ngôi sao thứ i có tâm nằm ở tọa độ ( A i , B i ) và bán kính R i . Những ngôi sao có thể đè lên nhau.
Chíp đứng ở trên mặt đất, tức là trục hoành, và nhìn thẳng lên trời. Chíp muốn biết ngôi sao gần nhất mà mình nhìn thấy được là ngôi sao nào, để có thể chọn chỗ đứng thích hợp ngắm ngôi sao mình thích. Vì vậy, Chíp đặt ra Q câu hỏi, mỗi câu hỏi gồm một số X i , hỏi rằng nếu đứng ở vị trí ( X i , 0) thì ngôi sao gần nhất Chíp nhìn thấy là ngôi sao nào.
Tại vị trí ( X i , 0), vẽ một tia song song và cùng chiều với trục tung, đường tròn đầu tiên nó chạm vào thì ngôi sao tương ứng với đường tròn đó là ngôi sao đầu tiên Chíp nhìn thấy. Bạn hãy giúp Chíp trả lời Q câu hỏi này nhé.
Input
Dòng đầu tiên gồm hai số nguyên N , Q .
N dòng tiếp theo, dòng thứ i gồm ba số nguyên A i , B i , R i mô tả ngôi sao thứ i .
Q dòng tiếp theo, dòng thứ i gồm một số nguyên X i mô tả truy vấn thứ i .
Output
In ra Q dòng, mỗi dòng gồm một số nguyên là chỉ số ngôi sao gần nhất Chíp nhìn thấy nếu đứng ở ( X i , 0). Nếu nhìn thấy được nhiều ngôi sao gần nhất thì in ra chỉ số của ngôi sao có chỉ số nhỏ nhất. Nếu tại vị trí đó nhìn thẳng lên không có ngôi sao nào thì in ra '-1'.
Giới hạn
1 ≤ N ≤ 50000.
1 ≤ Q ≤ 50000.
1 ≤ A i , B i , R i , X i ≤ 10 5 .
B i > R i (Những ngôi sao hoàn toàn cao hơn mặt đất).
40% số điểm có 1 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000.
Example
Input:4 5
2 3 2
6 9 2
5 5 2
4 7 3
4
7
8
1
9 Output:1
3
2
1
-1
- Người up: voj
- Nguồn bài: Vũ Phúc Hoàng