A problem related to: minkowski sum of two simple polygon

Revision en3, by steinum, 2021-05-17 18:03:33

I was trying to solve this problem : cf-497D

My solution idea : let $R_d(p) = p'$ where $p'$ is the new location of point $p$ if we rotate it $d$ degree counter-clockwise with respect to $(0,0)$.

Hence, for some point $a \in A$ and $b \in B$ we can write $R_d(a-p)+p = R_d(b-q)+q$.

$R_d(a-p)+p = R_d(b-q)+q$

$\Longrightarrow R_d(a)-R_d(p)+p = R_d(b)-R_d(q)+q$ [R_d() is actually a cross/dot function , hence we can separate it]

$\Longrightarrow p-q - R_d(p) + R_d(q)= R_d(b)-R_d(a)$

$\Longrightarrow (p-q) \frac{R_d - 1}{R_d}= a-b$

Here , $(p-q) \frac{R_d - 1}{R_d}$ actually represent a circle($C$) centered $p-q$ and radius = $|p-q|$.

And $a-b$ = Minkowski sum of A and (-B) [if we consider all $a$ and all $b$ ].

Hence, the problem turns into, checking if circle $C$ intersect polygon A-B or not.

My first idea was to triangulate $A$ and $-B$ then calculate the Minkowski sum of each pair, then check if the polygon(sum) intersect with circle $C$ or not.

I've written this code. I used the triangulation method mentioned in Computational geometry algorithms and applications-Springer-Verlag Berlin Heidelberg (2008) [page: 49]. But got WA on test 7.

Then I change my triangulation algorithm and use the Ear clipping method mentioned here. Here is my implementation($O(n^3)$). But again got WA on case 31.

I've read the editorial, and without triangulation, just take each pair of edge(one from $A$ and another one from $B$) and Minkowski sum them and got AC. My code.

Do we only need the borderline of the polygon here in this problem ? or my both triangulation code is wrong. Can you help me figure out, what have I done wrong, in my both code? And please share your triangulation code(both $n^2$ and $nlogn$ [with line sweep]).

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 steinum 2021-05-18 14:59:58 7
en3 steinum 2021-05-17 18:03:33 14 Tiny change: '$degree ccw with resp' -> '$ degree counter-clockwise with resp'
en2 steinum 2021-05-15 17:20:47 1 Tiny change: 'nd all $b$].\n\nHenc' -> 'nd all $b$ ].\n\nHenc'
en1 steinum 2021-05-15 17:18:04 2096 Initial revision (published)