It is well-known that the area of a triangle with vertices $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$ is given by
$$\frac{1}{2} |(y_2 - y_1)(x_3 - x_1) - (y_3 - y_1)(x_2 - x_1)|$$
(This equals zero if and only if the three points are collinear). Therefore, the condition that $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$ are non-collinear and twice the area of their triangle is not divisible by $p$ is equivalent to $(y_2 - y_1)(x_3 - x_1)$ and $(y_3 - y_1)(x_2 - x_1)$ being incongruent modulo $p$.

First, we show that $n = p + 2$ is impossible. Let $A_i(x_i, y_i)$ ($i = 1, \dots, p + 2$). If any three $x$-coordinates are congruent modulo $p$, then the corresponding three points form a triangle whose twice area is divisible by $p$. Otherwise, since $p + 2$ is odd, there exists one $x$-coordinate distinct modulo $p$ from all others. Without loss of generality, assume $x_1$ is distinct modulo $p$ from all other $x_i$. Consider the values $\frac{y_i - y_1}{x_i - x_1}$ modulo $p$ ($i = 2, \dots, p+2$). Since there are only $p$ possible residues, by the pigeonhole principle, two must be equal. If $\frac{y_i - y_1}{x_i - x_1} = \frac{y_j - y_1}{x_j - x_1}$ ($2 \le i < j \le p+2$), then $p$ divides $2S_{\triangle A_1A_iA_j}$.

Next, we construct an example with $n = p + 1$. Let $t$ be a quadratic non-residue modulo $p$. Consider pairs $(x, y)$ with $x, y \in \{0, 1, \dots, p-1\}$ satisfying $y^2 - tx^2 \equiv C \pmod{p}$ for some fixed $C \neq 0$. There are exactly $p+1$ such pairs (including $(0, 0)$ when $C = 0$, but we exclude this case).

We verify that these $p+1$ points satisfy the condition. For any three points $A_i, A_j, A_k$:
* If two have the same $x$-coordinate, their distance isn't divisible by $p$, and the height from the third point is a positive integer less than $p$, so twice the area isn't divisible by $p$.
* If all $x$-coordinates are distinct, we show $\frac{y_j - y_i}{x_j - x_i} \neq \frac{y_k - y_i}{x_k - x_i} \pmod{p}$. If they were equal to some $m$, then $y \equiv mx + r \pmod{p}$ would hold for three distinct $x$-values, implying $(mx+r)^2 - tx^2 \equiv C \pmod{p}$ has three solutions. This contradicts Lagrange's theorem since $m^2 \neq t \pmod{p}$ (as $t$ is a non-residue).

Therefore, the maximal $n$ is $p+1$. □