Four. (50 points) Given $n$ points $A_{1}, A_{2}, \cdots, A_{n}(n \geqslant 3)$ on a plane, no three points are collinear. Determine $k$ lines from $k$ point pairs (i.e., draw one line through each point pair of the $k$ point pairs), such that these $k$ lines do not form a triangle with all three vertices being given points. Find the maximum value of $k$.

保留源文本的换行和格式，翻译结果如下：

Four. (50 points) Given $n$ points $A_{1}, A_{2}, \cdots, A_{n}(n \geqslant 3)$ on a plane, no three points are collinear. Determine $k$ lines from $k$ point pairs (i.e., draw one line through each point pair of the $k$ point pairs), such that these $k$ lines do not form a triangle with all three vertices being given points. Find the maximum value of $k$.
Let the line passing through the point pair $A_{1}, A_{2}$ be $l$. This means $A_{1}, A_{2}$ cannot simultaneously connect to any of the remaining $n-2$ points, i.e., the number of lines passing through $A_{1}$ or $A_{2}$ is at most $n-1$ (including $l$).
At the same time, for the $n-2$ points $A_{3}, A_{4}, \cdots, A_{n}$, the number of lines passing through $A_{3}$ or $A_{4}$ is at most $n-3$, and so on, we get
$$
k \leqslant(n-1)+(n-3)+\cdots=\left\{\begin{array}{c}
\frac{n^{2}}{4}(n \text { is even }) \\
\frac{n^{2}-1}{4}(n \text { is odd })
\end{array}\right. \text {. }
$$

On the other hand, divide the $n$ points into two groups: when $n$ is even, each group has $\frac{n}{2}$ points; when $n$ is odd, one group has $\frac{n-1}{2}$ points, and the other group has $\frac{n+1}{2}$ points. Then connect each point in the first group to any point in the second group to form $\frac{n^{2}}{4}$ or $\frac{n^{2}-1}{4}$ lines. These lines clearly do not intersect to form a triangle with three vertices all being given points, hence the maximum value of $k$ is $\left\{\begin{array}{c}\frac{n^{2}}{4}(n \text { is even }) \\ \frac{n^{2}-1}{4}(n \text { is odd })\end{array}\right.$.