시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 67 28 25 65.789%

문제

창영이는 새로 구입한 감시 카메라 세 개를 이용해서 소 N 마리(1 ≤ N ≤ 50,000)를 감시하려고 한다.

i번째 소의 위치는 (xi, yi)이다. xi와 yi는 0보다 크거나 같고, 1,000,000,000보다 작거나 같은 정수이다. 두 소가 같은 좌표를 가지는 경우는 없다. 

상근이의 감시 카메라는 한 수직선 또는 수평선 위에 있는 모든 소를 감시할 수 있다.

감시 카메라 세 개를 이용해서 모든 소를 감시할 수 있는지 없는지 구하는 프로그램을 작성하시오.

즉, 점 N개를 선분 3개를 이용해서 덮을 수 있는지 구하는 문제이다.

입력

첫째 줄에 N이 주어진다. 둘째 줄부터 N개 줄에는 소의 좌표가 주어진다.

출력

모든 소를 감시 카메라로 감시할 수 있으면 1을 아니면 0을 출력한다. 

예제 입력

6
1 7
0 0
1 2
2 0
1 4
3 4

예제 출력

1

힌트

총 소가 6마리 있고, 소의 위치는 (1,7), (0,0), (1,2), (2,0), (1,4), (3,4) 이다. 감시 카메라를 y=0, x=1, y=4 로 설치하면 모든 소를 감시할 수 있다.