I used DP for solving this problem, and have AC in 0.015 sec. as many other Timus members. But, there are some members who take AC in 0.001 sec. So, my question is: is there some formula for this problem or this people take so incredible result with very hard optimization?
Start with sequence of anges 0, 90, 180, 270 (the inner square) and perform -45, +45 steps at every edge from previous stage. Then cut away 180 degree turns. After that number of remaining edges /2 will be the result for current stage. Of course, yhat won't work for big N, but it gives an idea on how to calculate number of 180-degree cut-outs at stage N. Case N=1 is special. Odd and even N should be treated separately. The rest is up to you :)