Here's the proof that the statement is true for even $n$ (I'll let someone else post a construction for odd $n$). Suppose there is a polygon $A_1A_2\ldots A_n$ with \[ \angle A_1 = \angle A_2 = \cdots =\angle A_{n-1} = 180^{\circ}-\theta \]and with sides of same length, say $1$, except possibly for the side $A_pA_{p+1}$. (Note the indices differ by $1$ from the previous solution.) Let \[ z = e^{i\theta} = \cos\theta + i \sin\theta. \]This time, we may impose complex coordinates such that \[ 1 = \overrightarrow{A_nA_1\vphantom{A^2}}, \quad z = \overrightarrow{A_1A_2\vphantom{A^2}}, \quad z^2 = \overrightarrow{A_2A_3\vphantom{A^2}}, \quad \ldots, \quad z^{n-1} =\overrightarrow{A_{n-1}A_n} \]except that $\overrightarrow{A_p A_{p+1}}$ is equal to a real multiple of $z^p$ rather than exactly equal to it; we denote this by $r \cdot z^p$ for $r \in {\mathbb R}$. Because of the convexity, we need $\theta < \frac{360^\circ}{n-1}$ (the complex numbers $z^0$, $z^1$, $z^2$ should have increasing argument since the original polygon was convex). We also have $z \ne 1$. As before, we have that the complex numbers here must sum to zero, so \begin{align*} 0 &= 1 + z + \dots + z^{p-1} + rz^p + z^{p+1} + \dots + z^{n-1} \\ &= [1+z+\dots+z^{n-1}] + (r-1)z^p \\ &= \frac{z^n-1}{z-1} + (r-1)z^p \\ \implies 1-r &= \frac{z^n-1}{z^p(z-1)}. \end{align*}Apparently, the right-hand side is a real number. So it should be equal to its complex conjugate. Since $|z| = 1$, we have $\bar z = 1/z$, so this occurs if \[ \frac{z^n-1}{z^p(z-1)} = \frac{z^{-n}-1}{z^{-p}(z^{-1}-1)}. \]Assume for contradiction now that $z^n \neq 1$ (otherwise we immediately have $r=1$ and the entire problem is solved). Then the equation implies \[ z^{n} = z^{2p+1}. \]Therefore, we have \[ (n-(2p+1)) \cdot \theta \]is an integer multiple of $360^\circ$. But $n-(2p+1)$ has absolute value strictly less than $n$, and is nonzero since $n$ is even. But $\theta < \frac{360^\circ}{n-1}$ and this is a contradiction.

v_Enhance wrote: Here's the proof that the statement is true for even $n$ (I'll let someone else post a construction for odd $n$). Suppose there is a polygon $A_1A_2\ldots A_n$ with \[ \angle A_1 = \angle A_2 = \cdots =\angle A_{n-1} = 180^{\circ}-\theta \]and with sides of same length, say $1$, except possibly for the side $A_pA_{p+1}$. (Note the indices differ by $1$ from the previous solution.) Let \[ z = e^{i\theta} = \cos\theta + i \sin\theta. \]This time, we may impose complex coordinates such that \[ 1 = \overrightarrow{A_nA_1\vphantom{A^2}}, \quad z = \overrightarrow{A_1A_2\vphantom{A^2}}, \quad z^2 = \overrightarrow{A_2A_3\vphantom{A^2}}, \quad \ldots, \quad z^{n-1} =\overrightarrow{A_{n-1}A_n} \]except that $\overrightarrow{A_p A_{p+1}}$ is equal to a real multiple of $z^p$ rather than exactly equal to it; we denote this by $r \cdot z^p$ for $r \in {\mathbb R}$. Because of the convexity, we need $\theta < \frac{360^\circ}{n-1}$ (the complex numbers $z^0$, $z^1$, $z^2$ should have increasing argument since the original polygon was convex). We also have $z \ne 1$. As before, we have that the complex numbers here must sum to zero, so \begin{align*} 0 &= 1 + z + \dots + z^{p-1} + rz^p + z^{p+1} + \dots + z^{n-1} \\ &= [1+z+\dots+z^{n-1}] + (r-1)z^p \\ &= \frac{z^n-1}{z-1} + (r-1)z^p \\ \implies 1-r &= \frac{z^n-1}{z^p(z-1)}. \end{align*}Apparently, the right-hand side is a real number. So it should be equal to its complex conjugate. Since $|z| = 1$, we have $\bar z = 1/z$, so this occurs if \[ \frac{z^n-1}{z^p(z-1)} = \frac{z^{-n}-1}{z^{-p}(z^{-1}-1)}. \]Assume for contradiction now that $z^n \neq 1$ (otherwise we immediately have $r=1$ and the entire problem is solved). Then the equation implies \[ z^{n} = z^{2p+1}. \]Therefore, we have \[ (n-(2p+1)) \cdot \theta \]is an integer multiple of $360^\circ$. But $n-(2p+1)$ has absolute value strictly less than $n$, and is nonzero since $n$ is even. But $\theta < \frac{360^\circ}{n-1}$ and this is a contradiction. Maybe I'm wrong,but in olympiad I made something else.I proofed that for n>3,all points should be cyclic and so all angles and all sides are equal to each other.

Here was my proof on the contest: For odd $n$, the construction is as follows. Start with a regular $n-$gon. Fix a side $A_0B_0$, and consider the vertex $P$ opposite that side. Let the other sides be $A_0A_1=\ldots=A_{m-1}A_m=A_mP$. Rotate the sides $A_iA_{i+1}$ outwards about $A_i$, all by the same small angles, as well as $A_{m}P$ around $A_m$ by that small angle. Do the same thing but in the other direction on the side of $B$. The point $P$ has two images in this rotated figure: $P_A, P_B$. For small enough angles, $P_AP_B<A_0B_0$, and notice that $P_AP_B\parallel A_0B_0$. Our construction is the polygon formed by $Q=A_0P_A\cap B_0P_B$, and apply the homothety that sends $P_A$ to $Q$ from $A_0$ that maps $A_i$ to $A_i'$, and same thing on the other side for $B$. To prove that even $n$ all work, consider the angle $A_0OB_0$ the only angle that is possibly unequal, and consider a coordinate plane where $O$ is the origin and the angle bisector of $A_0OB_0$ is the x-axis. It's easy to see using vectors that all sides must have the same length, as by the equal angles condition all other sides come in pairs with angles $\theta, -\theta$, and all but one pair must have equal length, and thus equal $x$-components. Since the vector sum of the $n$ sides starting from $OA_0$ is equal to the vector sum of all $n$ sides starting from $OB_0$, the last pair must also have equal $x$-components, and must thus have equal magnitudes. The preceding vector arguments that the point opposite $O$, call it $P$, lies on the $x$-axis. It now remains to show that $\angle A_0OB_0$ is equal to the other angles. Let the other sides be $A_0A_1=\ldots=A_{m-1}A_m=A_mP$ and define $B_i$ similarly. Observe that we can inductively show that $PA_iA_{i+1}A_{i+2}$ is cyclic, and note that $OA_0A_1A_2$ is an isosceles trapezoid, so all the points above the x-axis are cyclic. This implies that $POA_0A_m$ is cyclic, and from $OA_0=PA_m$, it must be an isosceles trapezoid, and thus by symmetry $\angle A_0OB_0=\angle A_mPB_m$.

omg hi InCtrl <3

omg hi khina <3

Fun problem. The answer is $n$ even only. First, we will construct a non-regular $\mathcal{P}$ for odd $n$ as follows. Fix $0<2\lambda<1$, and draw a segment of length $1+\lambda$ between $(0,0)$ and $(1+\lambda,0)$. For some $0^\circ\leq \theta\leq 180^\circ$, draw $\tfrac{n-1}{2}$ edges of length $2$ as follows: turn $\theta$ degrees to the left, draw an edge of length $2$, and repeat. Here's an example with $\theta=70^\circ$ and $n=7$: [asy][asy] pair A = (0,0); pair B = (1.5,0); pair C = B+dir(70)*2; pair D = C+dir(140)*2; pair E = D+dir(210)*2; draw(A--B--C--D--E); dot(E); [/asy][/asy] Consider the $x$-coordinate of the end of last edge, marked by a dot. Clearly it is a continuous function of $\theta$. When $\theta=\tfrac{360^\circ}{n-1}$, the $x$-value is $\lambda-1<0$, while when $\theta=\tfrac{360^\circ}{n}$, the $x$-value is $\theta>0$, so there must exist some value of $\theta$ where the $x$-value is $0$. Pick that value of $\theta$, and reflect the resulting broken line over the $y$-axis. This forms a non-regular polygon with $n$ sides, $n-1$ of which have length $2$ with the remaining edge having length $2+2\theta$, and with all angles equalling $\theta$ except for the one on $x=0$. We now prove that for $n$ even, $\mathcal{P}$ must be regular. Let $P_0\ldots P_{n-1}$ be the polygon, with $P_0P_1$ being the unequal side. Take indices $\pmod{n}$, and draw segments $P_iP_j$ for all $i+j=1$. Also suppose WLOG that $\angle P_k$ is unequal, where $k \leq n/2$. It is not difficult to prove that $P_iP_{n+1-i} \parallel P_0P_1$ for $2 \leq i \leq k$, as well as $P_iP_{n+1-i} \parallel P_{n/2}P_{n/2+1}$, so in fact all the drawn segments are parallel, and since all sides except for $P_0P_1$ are equal, all of the trapezoids of the form $P_iP_{i+1}P_{n-i}P_{n+1-i}$ are isosceles. But then $\angle P_k=\angle P_{n+1-k}$, so all angles should be equal. From here, it's easy to get that all the sides are equal too. $\blacksquare$

While solving this problem, I ended with something that would only be true if the polygon was convex, and it took me a while to realize that this was given in the problem statement... But now I am wondering if this problem is still true for concave (but not self-intersecting) polygons. This seems not hard, but I'm too lazy to do it.

The answer is $n$ even. The idea is to draw vectors along the sides of $\mathcal P$ and then translate the vectors to the origin. Since $\mathcal P$ is convex, consecutive sides become adjacent vectors. Thus $n-1$ of the angles between the $n$ vectors are equal, and $n-1$ of the vectors have equal length, and they sum to zero. If all vectors have equal length but not all angles are, then orient the internal bisector of the unequal angle vertically. Then all vectors are either shifted up or down from the regular $n$-gon, overlaid symmetrically. Thus the sum of the vectors cannot be zero. Otherwise, take the vector $V$ with different length and replace it by a vector $V'$ in the same direction with equal length to the others. Now the whole construction is symmetric about the internal bisector of the unequal angle (if all angles are equal pick one). Thus their sum must be in this direction or opposite it, but their sum is $V'-V$ which is in the same direction as $V.$ Thus $V$ lies along this axis of symmetry. In fact $V$ is the only vector that lies on this axis, since no vectors overlap and no vector occupies the side of the axis that is between the two consecutive vectors bounding the unequal angle. Thus the axis has one vector, and all other vectors are mirrored, so the total number of vectors must be odd. For $n$ odd a construction is to start with $n-1$ equally spaced equal length vectors, then duplicate one and double the length of the opposite one, then slightly push the two duplicates apart, making all other vectors move except the opposite one (like one of those chinese fan things), then adjust the length of the opposite one to fit. Then arrange all $n$ vectors consecutively.