평면 찾기

평면 밖의 점을 $X$라고 하자. 크기가 $4$ 이상인 점 번호 집합 $A$를 생각하자.

$X \notin A$라면 $A$의 모든 점은 $\Pi$ 위에 있으므로 질의의 답은 YES이다.

$X \in A$라면 $A$에는 $X$ 이외의 점이 적어도 세 개 있다. 이 세 점은 $\Pi$ 위에 있으며 일직선 위에 있지 않으므로 이들이 결정하는 유일한 평면은 $\Pi$이다. $X$는 위에 있지 않으므로 질의의 답은 이다.

따라서 크기가 $4$ 이상인 집합에 대한 질의는 그 집합에 $X$가 포함되어 있는지를 정확히 알려준다.

처음에는 후보 집합 $C=\{1,2,\cdots,N\}$으로 둔다. 항상 $X \in C$를 유지한다.

$|C|>9$인 동안 $C$를 크기가 거의 같은 두 집합 $A,B$로 나눈다. $A$를 질의한다. 답이 NO라면 $C=A$로 바꾸고, 답이 라면 로 바꾼다. 두 집합의 크기는 모두 이상이므로 앞의 판정이 항상 유효하다.

이 과정을 마치면 $5 \leq |C| \leq 9$이다. 각 $x \in C$에 대해 $C \setminus \{x\}$를 질의한다. 이 집합의 크기는 적어도 이다. 답이 인 유일한 경우가 인 경우이므로 답을 찾을 수 있다.

이분 과정에서 질의한 집합 크기의 합은 $N$보다 작다. 마지막 단계에서는 최대 $9$번, 매번 최대 $8$개의 점을 질의한다. 따라서 모든 질의의 $k$의 합은 $N+72$보다 작고, 이는 $100\,072$ 이하이다.

이분 질의를 $t$번 수행한 뒤의 후보 수를 $m$이라고 하자. $t \leq 13$이면 $m \leq 9$이므로 전체 질의 수는 $t+m \leq 22$이다. 라면 에서 이므로 전체 질의 수는 최대 이다. 따라서 항상 번 이하의 질의로 해결할 수 있다.

시간 복잡도는 출력한 점 번호의 수를 포함하여 $O(N)$이고, 메모리 복잡도는 $O(N)$이다.