Saving James Bond - Hard Version.rb

Bank = 50
n,d = STDIN.gets().split.map(&:to_i)
p = Array.new()

class Graph
    attr_accessor :edge, :nv
    def initialize (number = 0)
        @nv = number
        @edge = Array.new(number + 2) { Array.new() }
    end
    def addEdge (a, b)
        @edge[a].push(b)
        @edge[b].push(a)
    end
    def getEdges (vert)
        @edge[vert]
    end
end

class Point
    attr_accessor :x, :y
    protected :x=, :y=
    def initialize (x = 0, y = 0)
        @x, @y = x, y
    end
    def distance(p)
        (@x - p.x) ** 2 + (@y - p.y) ** 2
    end
end

def buildGraph (n, d, p)
    g = Graph.new(n)
    d0 = (7.5+d)**2
    center = Point.new
    n.times do |i|
        if center.distance(p[i]) <= d0
            g.addEdge(0, i+1)
        end
    end
    g.edge[0].sort_by! { |i| center.distance(p[i - 1])}


    n.times do |i|
        x = p[i].x
        x = -x if x < 0
        x = Bank - x
        y = p[i].y
        y = -y if y < 0
        y = Bank - y
        if x <= d || y <= d
            g.addEdge(n+1, i+1)
        end
    end

    squareD = d**2
    n.times do |i|
        for j in i+1...n
            if p[i].distance(p[j]) <= squareD
                g.addEdge(i+1, j+1)
            end
        end
    end

    return g
end

def bfs (g, p, n)
    visited = Array.new(n+2, false)
    path = Array.new(n + 2, 0)
    queue = Array.new
    queue.push(0)
    while queue.empty? == false
        cur = queue.shift
        if cur == n+1
            break;
        end
        for node in g.getEdges(cur)
            unless visited[node]
                visited[node] = true
                path[node] = cur
                queue.push(node)
            end
        end
    end
    res = Array.new
    now = path[n+1]
    while now != 0
        res.push(p[now - 1])
        now = path[now]
    end
    res.reverse
end

STDIN.each_line do |line|
    a = line.chomp.split.map(&:to_i)
    p.push(Point.new(a[0], a[1]))
end

if d >= Bank - 7.5
    puts 1
else
    array = bfs(buildGraph(n, d, p), p, n)
    if array.empty?
        puts 0
    else
        puts "#{array.length + 1}"
        for point in array
            puts "#{point.x} #{point.y}"
        end
    end
end