시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 128 MB | 44 | 13 | 11 | 37.931% |
엔트는 숲의 수호자이다. 중간계에서 가장 나이가 많은 엔트인 나무수염은 자신이 보호해야 하는 나무와 자신이 젊은 엔트 동료인 브레갈라드가 보호해야 하는 나무를 결정하려고 한다.
그들은 직사각형 모양의 팡고른 숲을 보호하고 있고, 이 숲의 나무는 짝수개이다. 나무수염은 직선 경계선을 그어 한 쪽은 자신이, 한 쪽은 브레갈라드의 구역으로 나눌 것이다. 만약, 각 구역에 있는 나무의 수와 면적이 다르다면 이들은 일 년에 한 마디씩 몇 만 년동안 싸울 것 이기 때문에, 공평하게 나누어야 한다.
만약 어떤 나무가 경계선 위에 있다면, 임의로 두 구역 중 하나에 속하게 할 수 있다. 두 구역에 모두 속하게 할 수는 없다.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 나무의 수 N, 숲의 너비 W, 숲의 높이 H가 주어진다. 숲의 꼭짓점은 (0,0), (W,0), (0,H), (W,H)가 된다. 다음 N개의 줄에는 나무의 좌표가 주어진다. (2 ≤ N ≤ 500000, 2 ≤ W,H ≤ 10000, N은 짝수, W와 H는 동시에 짝수가 아니다)
모든 나무의 좌표는 숲 안에 있고, (0 < x < W, 0 < y < H)를 만족한다. 나무의 위치가 겹치는 경우는 없다.
입력은 N = W = H = 0인 경우에 끝난다.
각 테스트 케이스에 대해서, N/2개 줄을 출력해야 한다. 각 줄은 나무수염이 보호하는 구역에 있는 나무의 좌표이다.
2 5 6 2 3 3 3 4 5 6 1 5 2 5 3 5 4 5 4 10 11 5 1 5 2 5 3 5 4 0 0 0
3 3 1 5 2 5 5 1 5 2