भार का संतुलन
Problem
<दिव>
किसान जॉन की गायें अलग-अलग बिंदुओं पर हैं (x1,y1)…(xn,yn ) इसके क्षेत्र (1≤N≤100,000, सभी xi और yi सकारात्मक विषम पूर्णांक हैं जो 1,000,000 से अधिक नहीं हैं। FD अपने क्षेत्र को अनंत की बाड़ के साथ विभाजित करना चाहता है लंबाई उत्तर से दक्षिण तक, समीकरण x = a द्वारा वर्णित (a एक सम पूर्णांक है, इसलिए यह सुनिश्चित किया जाता है कि बाड़ किसी भी गाय की स्थिति से नहीं गुजरती है।) वह अनंत लंबाई की बाड़ भी बनाना चाहता है। पूर्व से पश्चिम तक, जिसे समीकरण y=b द्वारा वर्णित किया गया है, जहां b एक सम पूर्णांक है ये दो बाड़ (a,b) पर प्रतिच्छेद करते हैं, और एक साथ क्षेत्र को चार क्षेत्रों में विभाजित करते हैं।
<दिव>
एफडी इस तरह से ए और बी चुनना चाहता है कि उन्हें "संतुलित" सभी क्षेत्रों में गायों की संख्या, यानी ताकि कोई ऐसा क्षेत्र न हो जिसमें बहुत अधिक गायें हों। बता दें कि एम इन चार क्षेत्रों में गायों की अधिकतम संख्या है, एफडी चाहता है कि एम जितना संभव हो उतना छोटा हो। M.
के लिए यह न्यूनतम संभव मान निर्धारित करने में FD की सहायता करें
<दिव>