COCI 2013/2014 - Contest 2- 직선 (LINIJE) > 문제은행 : 정보올림피아드&알고리즘




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를 그으면 우현이는 더 이상 직선을 그릴 수 없기 때문에 승유가 이기게 된다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP