n1313

Дана бесконечная плоскость с бесконечно мощным источником света в (0,0) и случайно расставленными на плоскости препятствиями. Требуется рассчитать тени, отбрасываемые препятствиями, при условии, что свет распространяется равномерно, прямолинейно и не отражается.

На практике оперировать бесконечностями неудобно, поэтому следует либо ограничить мощность источника света и считать все точки, находящиеся снаружи некоего радиуса R затененными, либо ограничить плоскость какими-то границами. Так или иначе, далее рассматривается случай с конечным набором точек. Разумно сосредоточиться на препятствиях, так как их меньше, чем точек на плоскости.

Для случая с нулем препятствий очевидно, что все точки освещены и никаких расчетов не требуется.

Для одиночного препятствия в виде точки (x,y) тень есть просто отрезок прямой, соединяющей источник света и препятствие-точку. Очевидно, что все точки (a,b) с a<x или b<y освещены и не требуют расчетов.

Для одиночного препятствия в форме отрезка (x1,y1)->(x2,y2) тень есть выпуклы

n1313

class Sudoku

    def initialize(string)

        @grid = string.gsub(/[^0-9]/, "").split('').map(&:to_i).each_slice(9).to_a

        @empty = []
        @possibles = Array.new(9){ [] }
        @grid.each_with_index do |row, r|
            row.each_with_index do |cell, c|