Блог пользователя WARush143

Автор WARush143, история, 8 лет назад, По-английски

Hi all,

I was solving this problem — https://community.topcoder.com/stat?c=problem_statement&pm=14357

I have reduced it to counting number of non-intersecting pair of polygons, but how do I do this? I have looked at other competitor's codes, and they involve fixing two points and counting clockwise and counterclockwise rotations with a third point, but I don't understand how and why this is used. Would appreciate any explanations!

Thanks

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If the polygons are non-intersecting, there's a line that separates them. It turns out that if you require this line to actually touch both polygons (let's call it a "tight" line), every pair of polygons is separable by exactly two distinct lines. So you can fix this line and count how many configurations there exist such that this line is a tight separating line and you'll count everything twice, which you can easily fix. You should handle configurations in which at least one color has less than 3 points separately.