Let R be the function that rotates a point D degrees counter clockwise w.r.t to origin O. then if p is a valid point then, R(b-p)+p = a, for some a, b belonging to polygons a and b. In the language of complex numbers, R is a complex number multiplication. So Rb - Rp + p = a -> a - Rb = (1-R)p.

So we can take the minkowski sum of polygon A and polygon -RB (polygon B rotated w.r.t. origin and scaled by -1) then scale the resultant polygon by 1/(1-R) to get the actual required locus of p.

Complexity O(n) or O(nlogn) depending upon the implementation of minkowski sum.

83%
Solution Ratio

AnachorEarliest,

Kuddus.6068Fastest, 0.2s

tmwilliamlin168Lightest, 9.1 MB

tmwilliamlin168Shortest, 1682B

Toph uses cookies. By continuing you agree to our Cookie Policy.