wizard.py

import numpy as np
import matplotlib.pyplot as plt
from collections import defaultdict
from matplotlib import animation
import matplotlib.patches as patches
import math

global_R = 0


def area_of_triangle(a, b, c):
    xa, ya = a
    xb, yb = b
    xc, yc = c
    return 0.5 * abs(xa * yb + xb * yc + xc * ya - xa * yc - xc * yb - xb * ya)


def get_points_inside_square(cx, cy, r, points):
    a = (cx - r, cy - r)
    b = (cx + r, cy - r)
    c = (cx + r, cy + r)
    d = (cx - r, cy + r)
    s = ((a[0] - d[0])**2 + (a[1] - d[1])**2)**0.5
    inside_points = []
    not_inside = []
    for p in points:
        pab = area_of_triangle(p, a, b)
        pbc = area_of_triangle(p, b, c)
        pcd = area_of_triangle(p, c, d)
        pda = area_of_triangle(p, d, a)
        if pab+pbc+pcd+pda == s*s:
            inside_points.append(p)
        else:
            not_inside.append(p)
    return inside_points, not_inside

def find_centers(point, r):
    """Given 1 point, find all possible integer centers searching in a square
    around that point. Note that this method can be imporved."""
    posx, posy = point
    centers = ((x, y)
               for x in np.arange(int(np.ceil(posx - r)), int(np.floor(posx + r)) + 1)
               for y in np.arange(int(np.ceil(posy - r)), int(np.floor(posy + r)) + 1)
               if (x - posx)**2 + (y - posy)**2 < r * r)
    return centers


def find_circle(points, r=2.2):
    """Find the best center"""
    d = defaultdict(int)
    for point in points:
        for center in find_centers(point, r):
            d[center] += 1
    return max(d, key=lambda x: d[x])


def find_translation(center, r, points):
    inside_points, not_inside = get_points_inside_square(
        center[0], center[1], r, points)
    max_in = 0
    for tx in np.arange(0 - center[0], 8.5 - center[0], 0.5):
        for ty in np.arange(0 - center[1], 8.5 - center[1], 0.5):
            in_points = [[x + tx, y + ty] for (x, y) in inside_points]
            cur_center = (center[0] + tx, center[1] + ty)
            cur_points = np.array(in_points + not_inside)
            in_points_len = len(get_points_inside_square(
                cur_center[0], cur_center[1], r, cur_points)[0])
            # xv, yv = cur_points.transpose()
            # fig = plt.figure()
            # ax = fig.add_subplot(111)
            # ax.set_aspect(1)
            # ax.scatter(xv, yv)
            # ax.add_artist(plt.Circle(
            #     cur_center, r, facecolor='g', alpha=.5, zorder=0))
            # plt.show()
            if in_points_len > max_in:
                max_in = in_points_len
    print(max_in)


def make_results():
    """Green circle is the best center. Red crosses are posible centers for some
    random point as an example"""
    numTests = int(input()) + 1
    for testcase in range(1, numTests):
        n, R = [int(x) for x in input().split()]
        global_R = R
        points = []
        for each in range(n):
            points.append([int(x) for x in input().split()])
        r = (R / (2 ** 0.5))
        center = find_circle(points, r)
        find_translation(center, r, points)

make_results()