#!/usr/bin/env python3
import random
W,H=140,110
pts=[(i+.5,j+.5) for j in range(H) for i in range(W)]
pos=[(x,y) for y in range(0,H+1,5) for x in range(0,W+1,5)]
masks=[sum(1<<k for k,(a,b) in enumerate(pts) if (a-x)**2+(b-y)**2<=400) for x,y in pos]
pc=lambda x:bin(x).count('1')
def uni(s):
 u=0
 for i in s:u|=masks[i]
 return u
def greedy(n,r):
 s=[];u=0
 for _ in range(n):
  vals=sorted((pc(u|m),i) for i,m in enumerate(masks) if i not in s)
  v,i=random.choice(vals[-r:]);s.append(i);u|=masks[i]
 return s
def local(s):
 cur=pc(uni(s))
 for it in range(5):
  best=cur;move=None;ss=set(s)
  for q in range(len(s)):
   u=uni(s[:q]+s[q+1:])
   for i,m in enumerate(masks):
    if i not in ss:
     v=pc(u|m)
     if v>best:best,move=v,(q,i)
  if move is None:break
  s[move[0]]=move[1];cur=best
 return cur,s
best=(0,[])
for r in [1,10,30,100]:
 v,s=local(greedy(11,r))
 if v>best[0]:best=v,s
 print(r,v,v/15400)
print('BEST',best[0],[pos[i] for i in best[1]])