t.muttaqueen's blog

By t.muttaqueen, history, 7 years ago, In English

Hello, This is a problem from dhaka regional'15

problem link: Honey King

In short, in a different kind of 2D plane you are given some points(10^5 maximum) in the plane. find the minimum hexagon such that all points lie inside the hexagon.

So for a cell (x, y), there are six surrounding cells, up(x, y − 1), down(x, y + 1), up_left(x − 1, y), down_right(x + 1, y), up_right(x + 1, y − 1) and down_left(x − 1, y + 1). For points (0, 0), (−1, 0) and (−2, 2), This is the hexagon witch includes minimum number of inner hexagons. Output the minimum number of inner hexagons. so 7 is the answer in this case.

Please give me some hints.

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems like too hard for me to solve :(

»
7 years ago, # |
  Vote: I like it +26 Vote: I do not like it
Hint 1
Hint 2
Hint 3
»
7 years ago, # |
Rev. 4   Vote: I like it +30 Vote: I do not like it

Using Binary search to find the length of a side of hexagon.

Then you can calculate the number of inner hexagons using the formula:

num = L*(L+1)*3+1

here is my code: code (may help...)