Selecting random points at general position
Here's an approach that I think achieves $O(n^2)$ running time, as long as the points are not too dense (as long as $n$ is not too large compared to the size of the region).

Store the set of all slopes of lines between any pair of points.  There are $O(n^2)$ pairs of points, and each pair of points determines line; add that line to the set.  I suggest you store this as a hash table that maps the slope $s$ to the set of pairs $(P,Q)$ of points which are at slope $s$ from each other.

Now to add a new point, pick a point $R$ uniformly at random.  Pair $R$ up with each other point, say $P$.  Compute the slope of the line from $P$ to $R$.  Look up that slope in the hash table, and see whether the corresponding set contains the point $P$.  The latter can be done in $O(1)$ expected time if you use suitable data structures for the hash table and for storing the set (in particular, the entry corresponding to slope $s$ can be a hash-set of all of the points that participate in a pair whose slope is $s$).  Since $R$ can be paired up with $n$ other points, this check will take $O(n)$ expected time.

Now as long as the number of points is not too dense (so that you don't reject a point more than a constant fraction of the time), the expected running time will be $O(n^2)$.