고속도로 설계 Interactive 컴파일 명령

부자인 석환이는 자신이 소유한 $N$개 도시에 새로운 고속 도로를 짓기로 했습니다. 각 도시는 이미 자신들이 바라는 고속도로와의 교차로의 위치를 석환이에게 알려줬습니다. 이 위치는 점으로 표현됩니다. 석환이는 고속도로는 직선 형태로만 짓는다는 정책을 고수합니다. 기적적으로, 두 개의 고속 도로만 지으면 모든 도시를 이을 수 있다는 것이 밝혀졌습니다. 즉, 두 개의 직선을 그어서 각 도시의 교차로가 두 직선 중 하나 위에 위치할 수 있도록 할 수 있습니다. 또한, 두 직선 모두 적어도 세 개 이상의 교차로를 포함하고 있으며, 두 직선의 교점 위에는 교차로가 있을 수 없습니다. 이 조건을 만족하는 두 직선이 유일하다는 것은 쉽게 증명할 수 있습니다. 석환이는 여러분에게 고속도로를 지어달라고 부탁했고, 따라서 여러분은 두 직선을 어디에 그을지 알고 싶습니다. 이를 위해 석환이에게 교차로의 위치를 알려 달라고 하자 석환이는 지학이가 알고 있으니 그에게 물어 보라고 했습니다. 하지만 지학이는 여러분에게 위치를 알려주는 대신 자신에게 임의의 세 교차로가 같은 선 상에 있는지 묻는 것만 허용했습니다. 한 번 물을 때마다 비용을 지불해야 하므로, 여러분은 질문을 가능한 한 적게 해야 합니다.

두 개의 점은 직선을 결정할 수 있으므로, 여러분이 할 일은 두 개의 직선에 대해 이 직선이 잇는 두 개의 교차로를 구하는 것입니다.

해야 할 일

여러분은 두 개의 고속도로 각각에 대해 이들이 잇는 두 개의 교차로를 가능한 한 질문을 적게 하여 알아내는 프로그램을 작성해야 합니다.

라이브러리

지학이에게 물어보기 위해, 여러분에게 세 종류의 작업을 지원하는 라이브러리 office가 주어집니다.

• GetN : 맨 처음 단 한 번 호출해야 합니다. 이 함수는 도시의 수 $N$을 돌려줍니다. 교차로에는 $1$부터 $N$까지의 자연수 번호가 붙어 있습니다.
• isOnLine: 세 개의 교차로 번호를 인자로 해서 호출해야 합니다. isOnLine(x,y,z)는 세 점 $x,y,z$가 같은 선 상에 있다면 1을, 그렇지 않다면 0을 돌려줍니다. 두 점은 항상 같은 선 상에 있다는 것을 명심하세요.
• Answer : 맨 마지막에 단 한 번 호출해야 합니다. 이는 여러분의 해를 제출한 후 프로그램을 종료합니다. Answer는 4개의 인자 a1, b1, a2, b2를 가지고 있습니다. a1과 b1은 첫 번째 고속도로가 잇는 두 교차로의 번호이고, a2와 b2는 다른 고속도로가 잇는 두 교차로의 번호입니다.

C/C++로 코드를 작성할 때

#include "office.h"

를 사용하세요.

실험

여러분에게 office 라이브러리의 구현이 담긴 <code>sample.zip</code>이 주어집니다. (파일명을 클릭해서 내려받을 수 있습니다. 공식 그레이더가 아니라 운영진이 만든 것입니다) 이 라이브러리는 표준 입력에서 데이터를 읽습니다. 첫 번째 줄에는 도시의 수를 입력해야 합니다. 두 번째 줄에는 첫 번째 고속도로가 잇는 교차로들의 번호를 입력해야 합니다. 입력을 종료하려면 -1 또는 EOF를 입력하면 됩니다. 다른 고속도로가 잇는 교차로들은 두 번째 줄에서 주어지지 않은 교차로들이 됩니다.

제한

• 도시의 수 $N$에 대해 $40 \le N \le 100 000.$
• 여러분의 프로그램은 표준 입출력을 포함해서 어떤 파일을 읽거나 작성해서는 안 됩니다.
• 메모리 제한 : 16 MB (그레이더는 1MB보다 적은 메모리를 사용합니다.)
• 시간 제한 : 1.0초
• C/C++ 함수 정의는 아래와 같습니다.

int GetN(void); 
int isOnLine(int x, int y, int z); 
void Answer(int a1, int b1, int a2, int b2);

채점 기준

그레이더는 미리 결정된 상황을 사용하지 않지만, 모순되는 답을 하지는 않습니다. 여러분의 답안은 이전에 지학이에게 한 질문에서 답을 정확히 유추해 낼 수 있을 때에만 정답 처리될 것입니다.

25개의 테스트 케이스가 있습니다. 여러분의 답이 정확하고 지학이에게 질문을 $K$번 했다면,

• $K \le N/2+2$라면 4점,
• $K \le 2N/3$이라면 2점,
• $K \le N-3$이라면 1점,
• 그렇지 않다면 0점

을 받게 됩니다. 그레이더는 여러분이 적어도 $N/3$번의 질문을 해야만 올바른 답을 찾을 수 있도록 답할 것입니다.