सबसे अधिक अंक एक निश्चित आकार वृत्त

Question

यह आया था जब एक दोस्त, एक प्रोग्रामिंग प्रतियोगिता के बारे में बात में संलग्न का पता लगाएं और हम आश्चर्य होता है कि सबसे अच्छा तरीका था:

बिंदुओं की एक सूची को देखते हुए, एक चक्र के केंद्र खोजने के पूर्व निर्धारित आकार का जो सबसे अधिक अंक शामिल करता है। यदि ऐसी कई मंडलियां हैं, तो उनमें से एक को ढूंढना ही महत्वपूर्ण है।

उदाहरण इनपुट: 1000 अंक, 500x500 अंतरिक्ष में, और 60 व्यास का एक चक्र।

Answer 1

मेरे सबसे अच्छा तरीका अब तक है:

हर मंडली अंक एक सबसे बाईं ओर बिंदु होना आवश्यक है। तो यह एक बिंदु के दाईं ओर सभी बिंदुओं की एक सूची बनाता है जो संभावित रूप से किसी सर्कल की सीमाओं के भीतर होते हैं। यह स्वीप सेन बनाने के लिए पहले x द्वारा बिंदुओं को टाइप करता है।

फिर यह फिर से उन्हें पड़ता है, इस बार पड़ोसियों की संख्या उनके पास है, ताकि अधिकांश पड़ोसियों के साथ बिंदु पहले जांच की जा सके।

फिर यह प्रत्येक बिंदु की जांच करता है, और प्रत्येक बिंदु के दाईं ओर, यह एक सर्कल की गणना करता है जहां बिंदुओं की यह जोड़ी बाएं परिधि पर होती है। फिर यह इस तरह के एक सर्कल के भीतर अंक की गणना करता है।

क्योंकि अंक संभावित रूप से क्रमबद्ध किए गए हैं, यह एक बार उन सभी नोड्स के रूप में माना जा सकता है जो संभावित रूप से बेहतर समाधान का कारण बन सकते हैं।

import random, math, time 
from Tkinter import * # our UI 

def sqr(x): 
    return x*x 

class Point: 
    def __init__(self,x,y): 
     self.x = float(x) 
     self.y = float(y) 
     self.left = 0 
     self.right = [] 
    def __repr__(self): 
     return "("+str(self.x)+","+str(self.y)+")" 
    def distance(self,other): 
     return math.sqrt(sqr(self.x-other.x)+sqr(self.y-other.y)) 

def equidist(left,right,dist): 
    u = (right.x-left.x) 
    v = (right.y-left.y) 
    if 0 != u: 
     r = math.sqrt(sqr(dist)-((sqr(u)+sqr(v))/4.)) 
     theta = math.atan(v/u) 
     x = left.x+(u/2)-(r*math.sin(theta)) 
     if x < left.x: 
      x = left.x+(u/2)+(r*math.sin(theta)) 
      y = left.y+(v/2)-(r*math.cos(theta)) 
     else: 
      y = left.y+(v/2)+(r*math.cos(theta)) 
    else: 
     theta = math.asin(v/(2*dist)) 
     x = left.x-(dist*math.cos(theta)) 
     y = left.y + (v/2) 
    return Point(x,y) 

class Vis: 
    def __init__(self): 
     self.frame = Frame(root) 
     self.canvas = Canvas(self.frame,bg="white",width=width,height=height) 
     self.canvas.pack() 
     self.frame.pack() 
     self.run() 
    def run(self): 
     self.count_calc0 = 0 
     self.count_calc1 = 0 
     self.count_calc2 = 0 
     self.count_calc3 = 0 
     self.count_calc4 = 0 
     self.count_calc5 = 0 
     self.prev_x = 0 
     self.best = -1 
     self.best_centre = [] 
     for self.sweep in xrange(0,len(points)): 
      self.count_calc0 += 1 
      if len(points[self.sweep].right) <= self.best: 
       break 
      self.calc(points[self.sweep]) 
     self.sweep = len(points) # so that draw() stops highlighting it 
     print "BEST",self.best+1, self.best_centre # count left-most point too 
     print "counts",self.count_calc0, self.count_calc1,self.count_calc2,self.count_calc3,self.count_calc4,self.count_calc5 
     self.draw() 
    def calc(self,p): 
     for self.right in p.right: 
      self.count_calc1 += 1 
      if (self.right.left + len(self.right.right)) < self.best: 
       # this can never help us 
       continue 
      self.count_calc2 += 1 
      self.centre = equidist(p,self.right,radius) 
      assert abs(self.centre.distance(p)-self.centre.distance(self.right)) < 1 
      count = 0 
      for p2 in p.right: 
       self.count_calc3 += 1 
       if self.centre.distance(p2) <= radius: 
        count += 1 
      if self.best < count: 
       self.count_calc4 += 4 
       self.best = count 
       self.best_centre = [self.centre] 
      elif self.best == count: 
       self.count_calc5 += 5 
       self.best_centre.append(self.centre) 
      self.draw() 
      self.frame.update() 
      time.sleep(0.1) 
    def draw(self): 
     self.canvas.delete(ALL) 
     # draw best circle 
     for best in self.best_centre: 
      self.canvas.create_oval(best.x-radius,best.y-radius,\ 
       best.x+radius+1,best.y+radius+1,fill="red",\ 
       outline="red") 
     # draw current circle 
     if self.sweep < len(points): 
      self.canvas.create_oval(self.centre.x-radius,self.centre.y-radius,\ 
       self.centre.x+radius+1,self.centre.y+radius+1,fill="pink",\ 
       outline="pink") 
     # draw all the connections 
     for p in points: 
      for p2 in p.right: 
       self.canvas.create_line(p.x,p.y,p2.x,p2.y,fill="lightGray") 
     # plot visited points 
     for i in xrange(0,self.sweep): 
      p = points[i] 
      self.canvas.create_line(p.x-2,p.y,p.x+3,p.y,fill="blue") 
      self.canvas.create_line(p.x,p.y-2,p.x,p.y+3,fill="blue") 
     # plot current point 
     if self.sweep < len(points): 
      p = points[self.sweep] 
      self.canvas.create_line(p.x-2,p.y,p.x+3,p.y,fill="red") 
      self.canvas.create_line(p.x,p.y-2,p.x,p.y+3,fill="red") 
      self.canvas.create_line(p.x,p.y,self.right.x,self.right.y,fill="red") 
      self.canvas.create_line(p.x,p.y,self.centre.x,self.centre.y,fill="cyan") 
      self.canvas.create_line(self.right.x,self.right.y,self.centre.x,self.centre.y,fill="cyan") 
     # plot unvisited points 
     for i in xrange(self.sweep+1,len(points)): 
      p = points[i] 
      self.canvas.create_line(p.x-2,p.y,p.x+3,p.y,fill="green") 
      self.canvas.create_line(p.x,p.y-2,p.x,p.y+3,fill="green") 

radius = 60 
diameter = radius*2 
width = 800 
height = 600 

points = [] 

# make some points 
for i in xrange(0,100): 
    points.append(Point(random.randrange(width),random.randrange(height))) 

# sort points for find-the-right sweep 
points.sort(lambda a, b: int(a.x)-int(b.x)) 

# work out those points to the right of each point 
for i in xrange(0,len(points)): 
    p = points[i] 
    for j in xrange(i+1,len(points)): 
     p2 = points[j] 
     if p2.x > (p.x+diameter): 
      break 
     if (abs(p.y-p2.y) <= diameter) and \ 
      p.distance(p2) < diameter: 
      p.right.append(p2) 
      p2.left += 1 

# sort points in potential order for sweep, point with most right first 
points.sort(lambda a, b: len(b.right)-len(a.right)) 

# debug 
for p in points: 
    print p, p.left, p.right 

# show it 
root = Tk() 
vis = Vis() 
root.mainloop() 

Answer 2

बहुत जल्दी विचार, जरूरी सही नहीं एक: - अंक जहां इसकी कवर चक्र के केंद्र हो सकता है की निरंतरता के

प्रत्येक बिंदु पी के लिए
• आप एक "उम्मीदवार को कवर क्षेत्र" की गणना। स्वाभाविक रूप से यह प्रत्येक बिंदु के लिए पी
• में केंद्र के साथ व्यास डी का एक चक्र भी है। आप अन्य बिंदुओं के संबंधित क्षेत्रों के साथ क्षेत्र को कवर करने वाले अपने उम्मीदवार को छेड़छाड़ करते हैं। क्षेत्रों को कवर करने वाले कुछ उम्मीदवार पी के साथ और एक दूसरे के साथ छेड़छाड़ कर सकते हैं। प्रत्येक चौराहे के लिए आप अंतरंग क्षेत्रों की संख्या गिनते हैं। उम्मीदवार क्षेत्रों में से अधिकांश द्वारा अंतरित एक आकृति एक कवर सर्कल के केंद्र के लिए एक उम्मीदवार क्षेत्र है जिसमें पी और जितना संभव हो उतना अन्य अंक शामिल हैं।
• चौराहों की सबसे बड़ी संख्या

एन^2 जटिलता होने के लिए लगता है के साथ एक उम्मीदवार क्षेत्रफल ज्ञात है, बशर्ते कि गणना के चक्र के आकार क्षेत्रों के चौराहों आसान है

Answer 3

कैसे एक क्लस्टरिंग कलन विधि का उपयोग के बारे में पहचान करने के लिए अंक का समूह फिर क्लस्टर को अधिकतम अंक के साथ पता लगाएं। क्लस्टर का औसत बिंदु लें जिसमें अधिकतम अंक आपके सर्कल के केंद्र के रूप में हों और फिर सर्कल खींचे।

MATLAB k-means algorithm की implementation का समर्थन करता है और इसे वापस एक 2-डी सरणी (एक मैट्रिक्स सटीक होना करने के लिए) क्लस्टर साधन और इसी क्लस्टर आईडी के देता है।

के-साधनों का एक प्रसिद्ध फ्लिप पक्ष हाथ से पहले के (क्लस्टर की संख्या) पर निर्णय ले रहा है। हालांकि इसे हल किया जा सकता है - कोई डेटा बिंदुओं से के के मूल्य को सीख सकता है। कृपया यह paper देखें।

मुझे आशा है कि इस मदद करता है।

चियर्स

Answer 4

जब तक मैं स्पष्ट कुछ मुझे लगता है कि एक सरल जवाब है नहीं छूटा है।

एक आयताकार क्षेत्र MXN, अंक पी की संख्या, त्रिज्या R के लिए:

• मानचित्र Initialise सभी शून्यों के लिए अपने MXN क्षेत्र के (जैसे 2 डी पूर्णांक की सरणी)
• अपने पी अंक से प्रत्येक के लिए
  • वेतन वृद्धि सभी नक्शा अंक त्रिज्या R भीतर अधिक से अधिक मूल्य के साथ 1
• ढूँढें मानचित्र तत्व द्वारा - इस चक्र आप कर रहे हैं के केंद्र होगा

यह ओ (पी) है, मानते हुए पी पी रुचि का चर है।