Найдите большинство точек включенным в круг фиксированного размера

Мой лучший подход до сих пор:

каждый круг, содержащий точки, должен иметь левую точку. Таким образом, он делает список всех точек справа от точки, потенциально в пределах окружности. Сначала он сортирует точки X, чтобы сделать Sweep Sane.

Затем он снова сортирует их, на этот раз по количеству соседей справа, что у них есть, так что точка с большинством соседей сначала изучатся.

Затем он осматривает каждую точку, а для каждой точки справа он вычисляет круг, где эта пара точек находится на левом периметре. Затем это считает точки в таком круге.

Поскольку точки были отсортированы по потенциалу, он может заранее, когда он считается всеми узлами, которые могут потенциально привести к лучшему решению.

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()