djin.sql

#
# В декартовой СК на плоскости имеется набор окружностей одинакового радиуаса r.
#
# Таблица с центрами окружностей:
#
#     create table p ( x int, y int );
#
# Нужно найти максимальное количество окружностей, которые польностью покроет 
# окружность указанного радиуса Rg
#
# Тестовые наборы:
# r = 1
# R = 1
# insert into p values (0,0), (0,1), (0,2), (0,3), (0,4);
# r = 1
# R = 4
# insert into p values (0, 0), (0, 2), (2, 0);
#
#     see http://www.youtube.com/watch?v=O97NBMlXAvc
#

delimiter //

drop function if exists djin//

create function djin(Rg int unsigned, r int unsigned)
  returns int unsigned
begin
  DECLARE Re INT;
  DECLARE ndx INT;

  SET Re = Rg - r;
  
  SET ndx = 1;
  
    # вычисляем кооринаты центров двух окружностей для каждой пары точек
    # затем находим количество точек, внутри каждой из окружностей
    # возвращаем максимум количества таких точек и центр соответствующей окружности
    return (select MAX(rr.count) from (select COUNT(p.x) as count
                from (  
                        select ndx = ndx + 1 as id, x_n - b * Re as x, y_n + a * Re as y 
                        from calc_p 
                    union 
                        select ndx = ndx + 1 as id, x_n + b * Re as x, y_n - a * Re as y 
                        from calc_p

                    ) as t, p 

                where sqrt(pow(p.x-t.x,2)+pow(p.y-t.y,2)) <= Re
                group by t.id ) as rr);
end//

delimiter ;

  drop table if exists p;

  create table p ( x int, y int );
  insert into p values (0, 0), (0, 2), (2, 0);

  # перебираем все пары точек
  create or replace view pp AS 
        select DISTINCT p.x as p_x, p.y as p_y, p1.x as p1_x, p1.y as p1_y 
        from p, p as p1 where NOT(p.x=p1.x AND p.y=p1.y);

  # вычисляем коеффициенты уравнений прямой и центры отрезков для каждой из пар точек
  create or replace view calc_p AS  
        select p1_x - p_x as a, p1_y - p_y as b, (p1_x + p_x) / 2 as x_n, (p1_y + p_y) / 2 as y_n 
        from pp;

  select djin(4, 1);