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:


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.


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.