| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 40 | 21 | 20 | 58.824% |
이 문제는 인터랙티브 문제이다.
좌표평면 위에 $N$개의 점이 있다. 각 점은 1ドル$번부터 $N$번까지의 번호가 붙어 있으며 $i$번째 점 $P_i$는 $(X_i, Y_i)$ $(-10,000円 \le X_i, Y_i \le 10,000円)$에 있다. 모든 점의 좌표는 정수이며 어떤 세 점도 한 직선 위에 있지 않다.
당신은 이 중 몇 개의 점을 골라 그 점들의 볼록 껍질에 포함되는 점을 인터랙터에게 최대 $\left\lceil \frac{N}{2} \right\rceil$번 물어볼 수 있다. 당신은 모든 점의 좌표를 알아내야 한다.
이 문제의 인터랙터는 적응적이지 않다. 즉, 인터랙터는 여러분의 질문에 따라 점의 좌표를 바꾸지 않는다.
첫 번째 줄에 점의 개수 $N$ $(10 \le N \le 100)$이 주어진다.
당신은 인터랙터에게 다음 쿼리를 최대 $\left\lceil \frac{N}{2} \right\rceil$번 요청할 수 있다.
? $M$ $A_1$ $A_2$ ... $A_M$ $(3 \le M \le N;$ 1ドル \le A_i \le N;$ $i \neq j$면 $A_i \neq A_j)$: $P_{A_1},ドル $P_{A_2},ドル $\cdots,ドル $P_{A_M}$의 볼록 껍질이 무엇인지 질문한다.
모든 점의 좌표를 알아냈다면 정답을 다음과 같이 출력하고 표준 출력 버퍼를 비우고 프로그램을 즉시 종료해야 한다. 즉시 종료하지 않는 경우 예상치 못한 결과를 얻을 수 있다.
! $x_1$ $y_1$ $x_2$ $y_2$ $...$ $x_N$ $y_N$
1ドル \le i \le N$을 만족하는 모든 정수 $i$에 대해 $x_i = X_i$이고 $y_i = Y_i$이면 맞았습니다!!를 받는다.
4 3 2 0 0 -1 0 1 3 0 -1 2 0 0 1
? 4 1 2 3 4 ? 3 1 2 3 ! 2 0 0 -1 0 1 1 0
위 예시는 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 개행 간격 등을 조절한 것으로, 실제 입출력과는 다르다. 또한 $N = 4$인 경우는 실제 테스트케이스에서 입력으로 주어지지 않는다.
프로그램은 처음 두 번의 질문과 문제의 조건에 의해 4ドル$번 점의 위치가 $(1, 0)$임을 알 수 있었지만 1ドル$ 3ドル$번 점의 순서는 알 수 없어 임의 순서로 배열하였다.
볼록 껍질은 주어진 점을 모두 포함하는 가장 작은 볼록 다각형이다. 볼록 껍질은 항상 유일하게 존재한다.
Contest > BOJ User Contest > 카툰컵 > Cartoon Cup: ONE C번