WARush143's blog

By WARush143, history, 8 years ago, In English

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

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

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

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.