Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

fofao_funk's blog

Simple Polygon problem
By fofao_funk, history, 9 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

»
9 years ago, # |
  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
  • »
    »
    9 years ago, # ^ |
      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