PROBLEM LINK:Author: Pavel Sheftelevich DIFFICULTY:MEDIUM PREREQUISITES:Geometry, Binary search, Angles PROBLEM:You are given an integer 0 < N < 360 denoting an angle. Your task is to decide if it is possible to divide this angle using only a straightedge and compass into N equal angles of size 1 degree. If it is possible, then you have to provide this contruction. BONUSIf you want to watch a very nice video about constructing using only a straightedge and compass, please look here. QUICK EXPLANATION:First we want to decide if it is possible to do this construction. Using a wellknown fact, we argue that it is only impossible to do this if N % 3 == 0. In order to prove that, we will show how to construct an angle of size 1 degree if N % 3 != 0. Moreover, knowing when it is possible can lead us to an easier construction based on dividing the original angle until we construct an angle of size 1 with sufficient precision. EXPLANATION:Based on a well known result that trisecting an arbitrary angle is impossible we argue that the only case when the construction is impossible is when N % 3 == 0. If N % 3 == 0, then construction is impossible because it implies that we can trisect the angle of size 3  contradiction. So we assume that N % 3 != 0. We will show that in that case we can construct an angle of size 1 which implies that we can divide the angle of size N into N equal angles of size 1. First construct an angle of size 36. Next, construct an angle of size 60 and bisect it in order to get an angle of size 30. Using these two angles construct an angle of size 6 using subtraction 36  30 = 6. Next, use bisection to divide an angle of size 6 into in order to get an angle of size 3. Finally, since N % 3 != 0, we can construct an angle of size 1 using an angle of size N and an angle of size 3  because you can construct an angle of size N  1 if N % 3 == 2 or you can construct an angle of size N + 1 if N % 3 == 1. In any case, you can use subtraction to construct an angle of size 1. It is clear that if you have an angle of size 1, you can "fill" the orginal angle of size N with N angles of size 1. Ok, we proved that it is possible to construct an angle of size 1 if N % 3 != 0. We can implement this construction proof in order to output the exact steps, but it is quite complicated. The second method which was widely used by contestants is to bisect an angle of size N until you construct an angle of size 1 with sufficient precision, which is a lot easier to implement. AUTHOR'S AND TESTER'S SOLUTIONS:To be uploaded soon. RELATED PROBLEMS:To be uploaded soon.
This question is marked "community wiki".
asked 16 Dec '14, 04:46

My solution is a bit different from this, it's based on the following fact: If you have an angle of size N and N is coprime to 360, 720 operations is sufficient to divide the whole plane into 360 angles of size 1. That's because you can construct angles of size 2N, 3N, ..., 360N (modulo 360). If N is coprime to 360, {N, 2N, 3N, ..., 360N} is a complete residue system modulo 360. Then you can easily find out all the points you need. If the initial N isn't coprime to 360, 1) If N % 2 = 0, you can bisect it again and again until N % 2 != 0; 2) If N % 5 = 0, you can construct an angle of size 36 and use addition. answered 16 Dec '14, 11:26

What was meant by
If I understood it properly, it's binary search to find angle 1°, but we can use the same for N%3 == 0 as I described here. answered 16 Dec '14, 13:57
You can try, but actually it is not possible to construct the EXACT 1 degree angle if N % 3 == 0 based on the fact that it is given in the editorial. The bottom line is that, the answer for this case is NO, but in practice you can construct an angle as close to 1 degree as you want in any case (but not exactly 1 degree if N % 3 == 0).
(16 Dec '14, 17:33)
I know, that it's not possible to create exactly 1 degree angle... ...and just now I realized there is:
That answers my question ;)
(16 Dec '14, 17:57)

I couldnt attempt this problem due to end sems :. However in whatever time I could give it, I found this  http://archive.maths.nuim.ie/staff/sbuckley/Papers/divide_angle.pdf which says that "For positive integer n there exists a construction by straightedge and compasses to divide an arbitrary angle into n equal parts if and only if n is a power of 2". As per the editorial n%3 != 0 so n could be 7 but the proof doesnt allow n=7. It would be great for someone to clear this to me. answered 16 Dec '14, 14:48
1
But one additional thing you have in your hands is this first angle. So at the beginning you have the angle on 7° and you just need to divide it. As shown above, you can do 7  3  3 = 1 ;)
(16 Dec '14, 15:11)
Ok I mixed up the two Ns. One is n parts and other n is the angle.
(16 Dec '14, 15:19)

Took a lot of submissions but finally got it. Pretty much same as what is done in the editorial. Take one edge, create a 60 degree angle from it (equilateral triangle), then create a pentagon such that the same side bisects one of the angles of the pentagon. You get a 12 degree angle. Bisect it twice, get a 3 degree angle. Replicate it all over the plane. If the angle given initially is a multiple of 3, no answer. If it is not, you will get an angle of 1 from the earlier replication. Replicate it again all over the plane and display the answer. Never been happier than this to get an AC. :) Great question. answered 16 Dec '14, 16:14

Is there an easy way to perform "angle copy" operation? Or maybe in general two circles intersection calculation? I was kind of lazy to calculate circle and line intersection so I did bisection that way:
Something similarly easy? This was first time I used OOP in competition, having Vector, Point, Circle and Line classes :D answered 16 Dec '14, 18:53
1
There does exist a simple way to perform "angle copying". Given an N degree angle AOB. 1.Construct a circle with center at point O, and radius equal to OA. 2.Construct a circle with center at point B, and radius equal to BA. Then the intersection point of the two circles C is what we need, and it's trivial that OA = OC, angle AOC is 2N degrees. Just rotate point A 2N degrees around point O, you can also get point C. So the calculation is much easier.
(18 Dec '14, 08:13)
Thanks I got it, this rotation seems like easy thing in Java  http://stackoverflow.com/a/9985640/384674
(18 Dec '14, 22:55)

should be
N % 3 != 0
, right?Right, it's now fixed.