के अंदर अंकों की कुल संख्या की गणना करना 2 मंडलियां हैं और उनके केंद्र तय किए गए हैं और उन्हें इनपुट के रूप में दिया जाएगा। फिर एन अंक होंगे, जिनमें से एक्स और वाई समन्वय इनपुट के रूप में दिए जाते हैं।2 सर्कल
अंत में, प्रश्न पूछे जाएंगे। प्रत्येक क्वेरी के लिए, दो मंडलियों का त्रिज्या (उन्हें आर 1 और आर 2 होने दें) दिया जाएगा। पहले सर्कल के अंदर बिंदुओं की कुल संख्या या प्रत्येक क्वेरी के लिए दूसरा सर्कल आउटपुट करें। एक बिंदु एक सर्कल के अंदर स्थित है यदि बिंदु से केंद्र तक की दूरी सर्कल के त्रिज्या से कम या बराबर है।
बाधाएं: एन, क्यू < = 10^6 आर 1, आर 2 < = 10^7 और प्रत्येक समन्वय के लिए, x | और | वाई | < = 10^6
मैं एक ओ (nlogn) या ओ (nlog^2n) preprocessing और फिर ओ (लॉगन) एल्गोरिदम प्रति क्वेरी की तलाश में हूं। ओ (एन) प्रति प्रश्न समाधान बहुत धीमा है। कोई विचार यह कैसे क्रैक करने के लिए?
दो सरणी बनाएं जो उनकी दूरी के अनुसार अंक रैंक करते हैं। यह सॉर्टिंग के लिए ओ (एन लॉग (एन)) लेता है। फिर संबंधित सर्कल में अंतिम बिंदु खोजने के लिए दोनों सरणी में प्रति क्वेरी एक बाइनरी खोज करें। यह ओ लेता है (लॉग (एन))। –
यदि कोई बिंदु दोनों सर्कल के अंदर स्थित है तो इसे दो बार गिना जाएगा – user2040997