Find the Plane

Let $X$ be the point outside the plane. Consider a set $A$ of at least four point indices.

If $X \notin A$, every selected point lies on $\Pi$, so the answer is YES.

If $X \in A$, the set also contains at least three points on $\Pi$. These three points are not collinear, so the unique plane containing them is $\Pi$. Since $X$ does not lie on $\Pi$, the answer is NO.

Therefore, a query containing at least four points tells us exactly whether the queried set contains $X$.

Initially, let the candidate set be $C=\{1,2,\cdots,N\}$. We maintain the invariant $X \in C$.

While $|C|>9$, split $C$ into two sets $A$ and $B$ whose sizes differ by at most one. Query $A$. If the answer is NO, replace $$ with . Otherwise, replace with . Both parts have size at least five, so the criterion above is always valid.

After this process, $5 \leq |C| \leq 9$. For every $x \in C$, query $C \setminus \{x\}$. This set has at least four points. The answer is exactly when , so this identifies the answer.

The sum of the queried set sizes during the halving phase is less than $N$. The final phase uses at most nine queries of at most eight points each. Thus, the sum of $k$ over all queries is less than $N+72$, which is at most $100\,072$.

Suppose the halving phase uses $t$ queries and leaves $m$ candidates. If $t \leq 13$, then $m \leq 9$, so the total number of queries is $t+m \leq 22$. If , then implies , so at most queries are used. Therefore, the algorithm always uses at most queries.

The time complexity, including all printed indices, is $O(N)$, and the memory complexity is $O(N)$.