निर्माण प्रक्रिया को अनुकूलित करें
आपको एक निर्माण कंपनी द्वारा इस काम पर रखा गया है कि भारी निर्माण सामग्रियों को एक स्थान से दूसरे स्थान तक ले जाने की प्रक्रिया को बेहतर (Optimize) किया जा सके।
निर्माण स्थल के आयाम एक आयत के रूप में दिए गए हैं, जिसकी चौड़ाई
w और ऊँचाई h है। इसे आप इस तरह समझ सकते हैं कि आयत का निचला बायाँ कोना बिन्दु (0, 0) पर है और इसका शीर्ष-दायाँ कोना (w, h) पर स्थित है। इस निर्माण स्थल का प्रवेश द्वार इसके निचले हिस्से के केंद्र में है।निर्माण स्थल पर कुल
n क्रेन (cranes) हैं, जिनकी अवस्थिति के रूप में दी गई है। ये क्रेन अपने जिब (jib) की पहुँच के दायरे में आने वाली सामग्रियों को उठा और स्थानांतरित कर सकती हैं। प्रत्येक क्रेन 360° घूम सकती है और इनकी पहुँच का त्रिज्या है।कंपनी के सामने कई गंतव्य बिंदु (destination points) हैं, और आपके पास यह जानने का काम है कि प्रवेश द्वार से उस बिंदु तक सामग्री पहुँचाने के लिए कम से कम कितने क्रेन का उपयोग करना पड़ेगा।
इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
w और h दिए जाते हैं (2 ≤ w, h ≤ 200) जहाँ w सम संख्या है।अगली पंक्ति में एक पूर्णांक
n (1 ≤ n ≤ 50) दिया जाता है, जो क्रेन की संख्या दर्शाता है।इसके बाद की
n पंक्तियों में क्रमशः तीन पूर्णांक होते हैं, जो क्रेन का स्थान (x_i, y_i) और उसकी पहुँच की त्रिज्या r_i को परिभाषित करते हैं (0 ≤ ≤ w, 0 ≤ ≤ h, 0 ≤ ≤ 200)।इसके बाद एक पूर्णांक
k (1 ≤ k ≤ 30) दिया जाता है, जो गंतव्य बिंदुओं की संख्या को दर्शाता है।अगली
k पंक्तियों में दो पूर्णांक (0 ≤ ≤ w, 0 ≤ ≤ h) होते हैं, जो प्रत्येक गंतव्य बिंदु के निर्देशांक होते हैं।आउटपुट
प्रोग्राम को
k पंक्तियों में हर गंतव्य बिंदु तक पहुँचने के लिए आवश्यक क्रेन की न्यूनतम संख्या प्रिंट करनी चाहिए। यदि किसी गंतव्य बिंदु तक पहुँचना संभव न हो, तो प्रोग्राम को Impossible प्रिंट करना चाहिए।उदाहरण
Input | इनपुट |
4 4
2
2 1 1
2 3 1
5
2 2
3 2
1 2
2 3
3 3 | 1
Impossible
Impossible
2
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB