Created by
cia_rana
last modified
| def parse_input(input)
n, *maru_batsu = input.split
[n.to_i, *maru_batsu.map{|e|e.split(?,).map{|e|[e[0].ord-65, e[1].ord-97]}}]
end
def initialize_map(points)
map = Array.new(27){Array.new(27){0}}
points.each{|x, y|
map[y+1][x+1] = 1
}
(1..26).each{|y|
(2..26).each{|x|
map[y][x] += map[y][x-1]
}
}
(2..26).each{|y|
(1..26).each{|x|
map[y][x] += map[y-1][x]
}
}
map
end
def solve(input)
n, maru_points, batsu_points = parse_input(input)
maru_map = initialize_map(maru_points)
batsu_map = initialize_map(batsu_points)
# 探索範囲はo,xの4隅またはマップ端に隣接しているので、探索範囲を絞る
xs, ys = (maru_points + batsu_points).transpose.map{|es|(es + es.map{|e|e+1} + [0, 26]).sort.uniq}
max_area = -1
(0..(ys.size-2)).each{|it|
(0..(xs.size-2)).each{|jl|
((it + 1)..(ys.size - 1)).each{|ib|
((jl + 1)..(xs.size - 1)).each{|jr|
t, l, b, r = ys[it], xs[jl], ys[ib], xs[jr]
break if batsu_map[b][r] - batsu_map[b][l] - batsu_map[t][r] + batsu_map[t][l] > 0
maru_num = maru_map[b][r] - maru_map[b][l] - maru_map[t][r] + maru_map[t][l]
break if maru_num > n
max_area = [max_area, (b - t) * (r - l)].max if maru_num == n
}
}
}
}
max_area < 0 ? ?- : max_area
end
puts solve(gets)
|