BOJ 34993 볼록 껍질과 쿼리

문제 링크입니다.

문제 요약

$1$번부터 $N$번까지 $N$개의 점이 있습니다. 어느 세 점도 한 직선 위에 있지 않습니다.

점들의 부분집합을 질문하면 그 볼록 껍질을 이루는 점들의 좌표를 순서 없이 답변받을 수 있습니다. $\lceil N/2 \rceil$회의 질문으로 모든 점의 좌표를 특정하세요.

풀이

$\vert S \vert = 3$인 모든 점 집합 $S$는 볼록 껍질입니다. 따라서 한 번의 질문으로 세 점의 좌표 후보들을 알 수 있습니다. 모든 점이 서로 다른 질문 집합에 속하도록 쿼리를 날려봅시다.

$N$이 홀수라고 가정하겠습니다. 1 2 3, 3 4 5, 5 6 7, … , N-2 N-1 N 까지 $\lfloor N/2 \rfloor$개의 질문으로 $3$번부터 $N-2$번 점의 좌표는 모두 특정할 수 있습니다. 남은 하나의 질문은 1 5 N 등으로 $1$, $N$번 점의 좌표를 확정하고, 그에 따라 $2$번 점과 $N-1$번 점의 좌표 역시 확정할 수 있습니다.

$N$이 짝수인 경우도 비슷한데, 이 경우에는 $\lfloor N/2 \rfloor$ 번째 질문이 N-3 N-2 N-1이 되고, $N$번 점의 좌표는 답변으로 한 번도 나오지 않은 상태가 됩니다. 1 N-1 N으로 세 점을 특정하고 $N$이 홀수일 때와 같은 방식으로 $2$번 점과 $N-1$번 점을 특정하면 됩니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int X[123], Y[123], n, m;
array<int, 6> qry[1234];

bool chk(int i, int j, int idx){
	return (qry[i][j] == X[idx]) && (qry[i][j+1] == Y[idx]);
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false); cin >> n;
	for(int i = 3; i <= n; i+=2){
		cout << "? 3 " << i-2 << ' ' << i-1 << ' ' << i << endl;
		cin >> m; for(int j = 0; j < 6; j++) cin >> qry[i][j];
	}
	for(int i = 5; i <= n; i+=2){
		for(int j = 0; j < 6; j += 2) for(int k = 0; k < 6; k += 2){
			if(qry[i-2][j] == qry[i][k] && qry[i-2][j+1] == qry[i][k+1]){
				X[i-2] = qry[i][k]; Y[i-2] = qry[i][k+1];
			}
		}
		if(i != 5) for(int j = 0; j < 6; j += 2){
			if(!chk(i-2, j, i-4) && !chk(i-2, j, i-2)){
				X[i-3] = qry[i-2][j]; Y[i-3] = qry[i-2][j+1];
			}
		}
	}
	if(n&1){
		cout << "? 3 1 5 " << n << endl;
		cin >> m; for(int j = 0; j < 6; j++) cin >> qry[1][j];
		for(int j = 0; j < 6; j += 2) for(int k = 0; k < 6; k += 2) if(qry[1][j] == qry[3][k] && qry[1][j+1] == qry[3][k+1]){
			X[1] = qry[1][j], Y[1] = qry[1][j+1];
		}
		for(int j = 0; j < 6; j += 2) if(!chk(3, j, 1) && !chk(3, j, 3)){
			X[2] = qry[3][j], Y[2] = qry[3][j+1];
		}
		for(int j = 0; j < 6; j += 2) for(int k = 0; k < 6; k += 2) if(qry[1][j] == qry[n][k] && qry[1][j+1] == qry[n][k+1]){
			X[n] = qry[1][j], Y[n] = qry[1][j+1];
		}
		for(int j = 0; j < 6; j += 2) if(!chk(n, j, n) && !chk(n, j, n-2)){
			X[n-1] = qry[n][j], Y[n-1] = qry[n][j+1];
		}
	}
	else{
		cout << "? 3 1 " << n-1 << ' ' << n << endl;
		cin >> m; for(int j = 0; j < 6; j++) cin >> qry[1][j];
		for(int j = 0; j < 6; j += 2) for(int k = 0; k < 6; k += 2) if(qry[1][j] == qry[3][k] && qry[1][j+1] == qry[3][k+1]){
			X[1] = qry[1][j], Y[1] = qry[1][j+1];
		}
		for(int j = 0; j < 6; j += 2) if(!chk(3, j, 1) && !chk(3, j, 3)){
			X[2] = qry[3][j], Y[2] = qry[3][j+1];
		}
		for(int j = 0; j < 6; j += 2) for(int k = 0; k < 6; k += 2) if(qry[1][j] == qry[n-1][k] && qry[1][j+1] == qry[n-1][k+1]){
			X[n-1] = qry[1][j], Y[n-1] = qry[1][j+1];
		}
		for(int j = 0; j < 6; j += 2) if(!chk(n-1, j, n-1) && !chk(n-1, j, n-3)){
			X[n-2] = qry[n-1][j], Y[n-2] = qry[n-1][j+1];
		}
		for(int j = 0; j < 6; j += 2) if(!chk(1, j, 1) && !chk(1, j, n-1)){
			X[n] = qry[1][j], Y[n] = qry[1][j+1];
		}
	}
	
	cout << "! "; for(int i = 1; i <= n; i++) cout << X[i] << ' ' << Y[i] << ' '; cout << endl;
}