시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 16 MB 10 2 (20%) 1
문제
정부는 N개의 도시에 새로운 고속도로를 건설할 계획을 세우고 있다. 각 도시의 위치는 이미 정해져 있고, 고속도로는 직선으로만 지어야 한다. 한 가지 다행인 사실은, 직선 고속도로 두 개만을 이용해서 모든 도시를 덮을 수 있도록 도시의 위치가 설계되어 있다는 것이다. 또한 각 직선이 적어도 3개 이상의 도시를 덮으며, 두 직선의 교점 위에는 어떠한 도시도 위치하지 않도록 두 직선을 설정할 수 있음도 보장되어 있다. (이처럼 그런 두 직선의 존재성이 보장되었을 경우, 그런 두 직선이 유일함은 쉽게 보일 수 있다.) 당신은 정부로부터 이러한 고속도로를 짓는 것을 위탁 받았고, 두 직선의 자취를 알아내야 한다. 단, 도시들의 좌표 정보는 국토교통부에서 보관하고 있고 당신은 국토교통부에 "세 도시 x, y, z가 한 직선 위에 있습니까?"라는 질문을 던지는 식으로만 정보를 얻어낼 수 있다. 이 질문은 한 번 던질 때마다 엄청난 수수료를 내야 하기 때문에 최대한 질문을 적게 하는 것이 중요하다. 위 조건을 만족하기 위해서는 두 직선 고속도로를 어디에 설정해야 하는지 알아내는 프로그램을 작성하라. (평면에서 어떤 직선은 그 직선 위에 있는 두 점에 의해 유일하게 정의되므로, 각 직선 고속도로에 대해 그 위에 있는 두 도시를 명시함으로써 당신의 답을 표현할 수 있다.)
입력
#### 라이브러리 국토교통부에게 질문을 하기 위해서, office라는 라이브러리를 이용한다. (``#include "office.h"``) **단, 당신이 작성한 프로그램은 어떠한 표준 입출력 혹은 파일 입출력을 해서는 안 된다.** office 라이브러리에서 함수의 정의는 아래와 같이 되어있다. ``` int GetN(void); int isOnLine(int x, int y, int z); void Answer(int a1, int b1, int a2, int b2); ``` - ``GetN`` : 프로그램을 시작할 때 아무 인자 없이 한 번만 호출하라. 이 함수는 리턴 값으로 도시의 개수 N을 반환한다. 도시의 번호는 1부터 N까지 붙여진다. - ``isOnLine`` : 국토교통부에 질문을 하는 데 쓰는 함수이다. 이 함수는 1부터 N까지의 도시번호 세 개를 인자로 가지고 ``isOnLine(x,y,z)``와 같이 호출되며, 만일 세 도시 x,y,z가 일직선으로 위치한다면 1을, 그렇지 않다면 0을 리턴 값으로 반환한다. 두 개의 도시는 항상 일직선 위에 위치함에 유의하라. - ``Answer`` : 모든 작업을 끝낼 때 답을 인자로 넘겨주면서 ``Answer(a1,b1,a2,b2)``와 같이 한 번만 호출하라. a1과 b1은 한 직선 고속도로 위에 있는 두 도시의 번호이며, a2와 b2는 그와는 다른 한 직선 고속도로 위에 있는 두 도시의 번호여야 한다. #### 실험 [sample.zip](http://koitp.org/download_file/fa0a559548fe148e4dd9a460aba52197fbf7322cbab2e00956d92cb09d19f575/sample.zip/) 파일 안에 있는 office 라이브러리를 사용할 수 있다. (단, 실제 채점 시에도 이 office.cpp를 사용하지는 않을 것이다.) 이 라이브러리는 표준 입출력으로부터 데이터를 다음과 같은 형식으로 입력 받는다. 첫 번째 줄에는 도시의 수를 나타내는 정수 하나가 주어져야 한다. 두 번째 줄에는 한 고속도로 위에 위치한 도시들의 번호가 빈 칸을 사이에 두고 주어져야 한다. 여기에 등장하지 않은 도시들은 모두 다른 한 고속도로 위에 위치한다고 간주한다. #### 제한 도시의 개수 N은 20 $\leq$ N $\leq$ 100,000를 만족한다. 메모리 제한: 16MB (라이브러리가 사용하는 메모리는 1MB 이하임이 보장된다.) 시간 제한: 1.0초
출력
힌트
#### 채점 국토교통부의 역할을 하는 채점 서버에서는 도시의 위치를 모두 미리 확정 지어 놓지 않는다. 다만, 당신이 isOnLine을 호출할 때마다 어떤 대답을 주었는지 기억해두고, 다음 isOnLine 호출에 대해서는 이때까지 준 대답에 모순되지 않는 범위 내에서 임의로 대답을 할 것이다. 만일 당신의 프로그램이 현재까지 얻은 정보만으로는 최종 답을 확신할 수 없는 시점에서 섣불리 Answer를 호출한다면, 즉 정확한 답을 알 수 없는데 찍었다면 답이 맞았다고 해도 점수를 받을 수 없다. 총 25개의 테스트 케이스가 있고 각 테스트 케이스에 대해 0, 1, 2, 3, 4점을 받을 수 있다. 당신이 Answer로 호출한 답이 틀릴 경우 0점이고, 맞을 경우 당신이 isOnLine을 호출한 횟수를 K에 따라 각각 아래 점수를 획득할 수 있다. - K $\leq$ N/2+2일 경우 4점 - K $\leq$ 2N/3일 경우 2점 - K $\leq$ N-3일 경우 1점 - 그 외의 경우 0점 채점 서버는 당신의 프로그램이 적어도 isOnLine을 N/3번 이상은 호출해야 정확한 답을 얻을 수 있는 쪽으로 isOnLine에 대한 답을 줄 것이다.