The problem is here. the formula used in majority of the solutions is 1 / 2sin(pi/4n). Can someone explain how one might reach to the formula ? @everule1 @waqar_ahmad224 @vijju123
The polygon has 2n sides.
Let us first find the length of the diagonal d. Let’s start by drawing the longest diagonal from each vertex.
We know that the angle between the diagonals is \theta=360/2n. Let \alpha be the other 2 angles in the triangle formed by the diagonals. \alpha = (180 -\theta)/2. We know that \alpha is opposite to the side with length d/2 and \theta is opposite to the side with length 1.
By sin rule we have \frac{d/2}{\sin\alpha} = \frac{1}{\sin{\theta}}. Therefore d=\frac{2\sin\alpha}{\sin \theta}.
Let us substitute the values.
2\sin\alpha = 2 \sin{((180 - 360/2n)/2)}= 2\sin(90 - 90/n)= 2\cos{90/n}.
\sin\theta = sin{360/2n}=\sin{180/n}.
Let \beta=90/n.
d=\frac{2\cos\beta}{\sin(2\beta)} = \frac{2\cos \beta \sin\beta}{\sin2\beta \sin\beta} = \frac{\sin2\beta}{\sin 2\beta\sin\beta} = \frac{1}{\sin\beta} = \frac{1}{\sin(90/n)}.
Now we know the length of the diagonal.
Let us put two opposing points on the cartesian plane with co-ordinates (d/2, 0), (-d/2, 0).
Since we have an even number of points are polygon is symmetric about the x axis and y axis. So let’s just look at the first quadrant for now.
Now let us see what a square looks like.
We can define a square as |x|+ |y|=c, which is a square with length c\sqrt{2}.
We know this because the graph will change direction at x=0 and y=0, and it can be seen trivially that it will pass through the points (\pm c, 0) and (0, \pm c) and that it will be a linear equation at every segment. It can be seen that a point (a,b) is inside the square if |a| + |b|\le c.
This is just a quick visualisation of what a square following this equation looks like.
We can see that we want to find the maximum of |x|+|y| in our polygon, as that will be the minimum value of c.
For now I will use a term vertical angle, which we will define as the angle between the vertical line passing through some point P, and the edge to it’s left in the first quadrant for convenience.
Let \theta=360/2n, which is equal to the external angle of the polygon.
Since the polygon i symmetric about the x axis, we can claim that the vertical angle of the rightmost point is \theta/2. We can see that the angle increases by $\theta$at every point when we go counter clock-wise. Let \alpha denote the vertical angle. We can see by basic trigonometry, that the change in x is -sin(\alpha) and the change in y is +cos(\alpha).
Therefore we want a k such that
\sum_{i=0}^k cos(\theta/2 + i\theta) - sin(\theta/2 + i\theta) is maximised.
We can see that this value will increase until \theta/2 + i\theta \ge 45, because after that cos(\theta/2 + i\theta) < sin(\theta/2 + i\theta). So we want maximum k such that \theta/2 + k\theta\le 45. Let us substitute the value of \theta.
90/n + 180k/n \le 45
2 + 4k \le n. Since k must be an integer, we know that k=\lfloor (n-2)/4\rfloor
Now
\sum_{i=0}^k \cos(\theta/2 + i\theta) - \sin(\theta/2 + i\theta)
=\sum_{i=0}^k \cos(\theta/2 + i\theta) - \sum_{i=0}^k\sin(\theta/2 + i\theta)
=\frac{\sin{(k+1)\theta/2}}{\sin \theta/2}\cos(\theta/2 + \frac{k\theta}{2})-\frac{\sin{(k+1)\theta/2}}{\sin \theta/2}\sin(\theta/2 + \frac{k\theta}{2})
=\frac{\sin{(k+1)\theta/2}}{\sin \theta/2}\sqrt{2}\sin{(45-\theta/2 - \frac{k\theta}{2})}.
Okay I’m stuck now. I’ll update when I figure it out, but it’s O(1) already.
13 Likes
Every time I look at your explanation and just wonder , man how this guy explains so beautifully.
with all formula’s , pictorial explanation etc. you spend a fair amount of time in this.
5 Likes
sir the way you explained it with those text,numbers,pics ,math…
thank you sir.