This problem was proposed by Swistak.

This is a rough sketch, and I'm not sure whether the parts I omit are easy or not (because I'm terrible at combinatorial geometry), but here it is. First, prove that any good polyline looks like a counterclockwise spiral. Given this, prove that once you fix the starting point of the spiral, the rest of the thing is completely defined. (This might be easier to be split into two parts: first, prove with first two points fixed, then prove with only the first point fixed.) Now that it's proven, we have $k \le n$; just give a regular $n$-gon to show $k \ge n$.

chaotic_iak wrote: This is a rough sketch, and I'm not sure whether the parts I omit are easy or not (because I'm terrible at combinatorial geometry), but here it is. First, prove that any good polyline looks like a counterclockwise spiral. Given this, prove that once you fix the starting point of the spiral, the rest of the thing is completely defined. (This might be easier to be split into two parts: first, prove with first two points fixed, then prove with only the first point fixed.) Now that it's proven, we have $k \le n$; just give a regular $n$-gon to show $k \ge n$. This is wrong, consider three points $A, B, C$ forming a ccw oriented triangle $\triangle ABC$ and a point $D$ inside it. Then there are six ccw oriented polylines with vertices in the given points: $DABC, DBCA, DCAB, ABCD, BCAD, CABD$. In particular, it is not true that if you fix the first point of the spiral, the rest is completely defined.

Oh, oops. That's right; the spiral can either go inside or go outside. Something something I'm terrible at combinatorial geometry.

A very beautiful problem!

Solved with Th3Numb3rThr33. Let $\mathcal H=\{H_1,\ldots,H_k\}$ be the convex hull, with the points $H_1$, $H_2$, $\ldots$, $H_k$ on $\mathcal H$ in counterclockwise order. Claim: No subsequence of the polyline is of the form $H_iQ_1\cdots Q_kH_j$, where $Q_1,\ldots,Q_k\notin\mathcal H$. In other words, we cannot leave the convex hull and return to it. Proof. Assume for contradiction otherwise. Then I claim we never reach $H_t$ for $t\notin\{i,i+1,\ldots,j\}$. By symmetry it suffices to show that we never reach $H_t$ after $H_j$. Indeed, we are henceforth trapped in the region defined by segments $H_iQ_1$, $Q_1Q_2$, $\ldots$, $Q_kH_j$ and the rays $H_{i-1}H_i$, $H_{j+1}H_j$. The claim follows. $\blacksquare$ Hence the path is of the form $A_iA_{i-1}\cdots A_1H_tH_{t+1}\cdots H_{t-1}B_1B_2\cdots B_j$. Let $\mathcal A=\{A_i,\ldots,A_1\}$, $\mathcal B=\{B_1,\ldots,B_j\}$. Claim: There is a line intersecting segment $H_tH_{t-1}$ that divides $\mathcal A$, $\mathcal B$. Proof. Note that $\mathcal A$ is always on one side of $\overline{H_tA_1}$ and $\mathcal B$ is always on one side of $\overline{H_{t-1}B_1}$. Hence any line between segments $H_tA_1$, $H_{t-1}B_1$ works. $\blacksquare$ Claim: The choice of $t$, $\mathcal A$, $\mathcal B$ (where a line intersects $\overline{H_tH_{t-1}}$ and divides $\mathcal A$, $\mathcal B$) uniquely determines the polyline. Proof. For convenience let $A_0=H_t$. Then for $\ell\ge0$, it is easy to check line $A_\ell A_{\ell+1}$ splits the plane into two half-planes, one of which contains $A_\ell$, $A_{\ell+1}$, $\ldots$, $A_i$. Hence $A_\ell$ uniquely determines $A_{\ell+1}$ for $\ell\ge0$, so $A_1$, $\ldots$, $A_i$ are determined. Similarly $B_1$, $\ldots$, $B_j$ are determined, as claimed. $\blacksquare$ Let $\mathcal G$ be the set of points in the polyline not in $\mathcal H$, so $|\mathcal G|=n-k$. Let there be $v_t$ points on $\overline{H_tH_{t-1}}$ that lie on line $UV$ for some $U,V\in\mathcal G$. Say a $t$-partitioner is a line through $\overline{H_tH_{t-1}}$ partitioning $\mathcal G$ into two sets (where $t$-partitioners are equivalent if they partition $\mathcal G$ into the same two sets). The goal is to compute the total number of partitioners. Claim: The number of $t$-partitioners is $n-k+1+v_t$. Proof. Situate a moving point $M$ on $\overline{H_tH_{t-1}}$ starting at $H_t$. Initially there are $n-k+1$ different partitioners through $M$. For each $U,V\in\mathcal G$ such that line $UV$ intersects $\overline{H_tH_{t-1}}$, note that as $M$ crosses $\overline{H_tH_{t-1}}\cap\overline{UV}$, one partition swaps $U$, $V$, so the number of partitioners is incremented. There are $v_t$ such instances where the number of partitioners is incremented, so the number of $t$-partitioners is $n-k+1+v_t$, as claimed. $\blacksquare$ Finally, the number of partitioners is \[\sum_{t=1}^k(n-k+1+v_t)=k(n-k+1)+2\binom{n-k}2.\]This is strictly decreasing, so it is maximized at $k=3$. The answer is $n^2-4n+6$.