fofao_funk's blog

Simple Polygon problem
By fofao_funk, history, 11 years ago, In English

Hi.

Can someone give me tips on how to solve problem I from NWERC 2009?

I've tried to solve it using something like a merge of many convex hulls but, besides being too complicated, the time complexity of this approach is quite high.

Any help is appreciated. Thanks!

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

»
11 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

There are maybe a lot of techniques to create the polygon. One that came to my mind is to create a lower hull, and then add the other points in the top part of the polygon sorted by x coordinate, and the tie breaker is y coordinate.

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

    I was looking into the same problem and your solution works, got AC.

    Thanks man!!

    → Reply