2
$\begingroup$

I need to create an algorithm that will output the number of self-crossings for an irregular orientation of an n-pointed star, whose vertices lie on the boundary of a circle. The sample input is as follows:

5
24.0
168.0
312.0
96.0
240.0

Where the first integer is n (the number of vertices), proceeded with n lines, each describing the positions of the vertices, taken in order, which form the star. Each vertex is in a unique position on the boundary of the unit circle, specified in degrees from the normal axis. All degree measures will be in the range [0,360).

The sample output for the sample input would be:

5 crossings

To tackle this problem, I was thinking of maybe separating the unit circle into quadrants and determine whether there are crossings depending on the positions of the vertices in their respective quadrants. However, I haven't been able to think of a way to implement this.

I was wondering if anyone could provide perhaps a high-level idea or a push in the right direction which could help me think of an algorithm.

Thank you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.