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
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.