2671 : 직선 (LINIJE)
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 7 회
- 시도횟수
- 14 회
문제
승유와 우현이는 N개의 점이 찍혀 있는 좌표평면 상에서 게임을 한다. 승유가 먼저 한 개 이상의 점을 지나는 직선을 긋는다. 그러면 우현이는 승유가 그었던 직선과 만나는 직선을 긋는데, 이 때 우현이는 승유가 그었던 직선위 N개의 점 중 하나를 선택하여야 한다. 우현이가 직선을 그은 다음에는 다시 승유가 직선을 긋는다.
직선은 x축 또는 y축과 평행해야 하며, 이미 그어진 직선과 겹치게 직선을 그으면 안 된다.
게임은 누군가가 직선을 더 이상 긋지 못할 때까지 진행되며, 이 때 직선을 긋지 못하는 사람이 진다.
점들의 정보가 주어질 때, 필승 전략을 갖고 있는 사람을 구하여라.
입력형식
입력은 3개의 테스트케이스로 이루어져있다.
각 테스트케이스의 첫 번째 줄에는 점의 수 N이 주어진다. (1 ≤ N ≤ 10,000)
두 번째 줄부터 N개의 줄에는 각 점의 좌표가 주어진다. 좌표는 1 이상 500 이하의 정수이다.
전체 데이터의 40%는 1 ≤ N ≤ 10이다.
출력형식
승유가 필승 전략을 갖고 있다면 1 를 출력한다. 그렇지 않으면 2 를 출력한다.
입력 예3 1 1 1 2 1 3 4 1 1 1 2 2 1 2 2 5 1 3 2 2 3 2 3 1 3 3 |
출력 예1 2 2 |
Hint!
승유가 직선 y=1을 그으면 우현이는 x=1을 긋게 된다. 그 후 승유가 직선 y=2를 그으면 우현이는 더 이상 직선을 그릴 수 없기 때문에 승유가 이기게 된다.