WIL's blog

Doubt about a geometry problem?
By WIL, 10 years ago, In English

The problem is Fence the vegetables from "2014 Caribbean Finals of the ACM-ICPC" in caribbean online judged.

I think that the minimum perimeter, is equals to:
(maxX-minX+1)*2+(maxY-minY+1)*2
But i dont know how find the minimum area with this perimeter. Thank for the help!!!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I think using Pick's theorem might work here

Pick's Theorem

Looks like I missed that " can't be non parallel to axis " , in which case using this will be overcomplicated unnecessary.

The best thing is to find the extreme points, find the area of that , then subtract the area of the pieces you would remove to get the original shape

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank for the answer, but i don't think this problem can be solved by this theorem, i analysed a bit more the problem and i think this can be solve by sweepline algorithm.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The fixed link

→ Reply