레이팅 미적용농부 존(Farmer John)은 새로 구입한 감시 시스템으로 N마리 (1 <= N <= 50,000)의 소들을 감시하고 싶어 한다.
i번째 소는 정수 좌표 (0...1,000,000,000 범위)의 위치 (x_i, y_i)에 있으며, 어떤 두 소도 같은 위치에 있지 않다. FJ의 감시 시스템에는 세 대의 특수 카메라가 있는데, 각 카메라는 수직선 또는 수평선 하나를 따라 있는 모든 소를 관찰할 수 있다. FJ가 이 세 카메라를 설치하여 N마리의 소를 모두 감시할 수 있는지 판정하시오. 즉, 소들의 N개 위치가 수평 또는 수직 방향의 세 직선의 집합으로 동시에 모두 "덮일" 수 있는지 판정하시오.
첫째 줄: 정수 N.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 소 i의 위치를 나타내는, 공백으로 구분된 정수 x_i와 y_i가 주어진다.
세 대의 카메라로 N마리의 소를 모두 감시할 수 있으면 1을, 그렇지 않으면 0을 출력한다.
3lines.in · 출력을 쓸 파일 3lines.out6
1 7
0 0
1 2
2 0
1 4
3 41Input details: There are 6 cows, at positions (1,7), (0,0), (1,2), (2,0), (1,4), and (3,4).
Output details: The lines y=0, x=1, and y=4 are each either horizontal or vertical, and collectively they contain all N of the cow locations.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > US Open > Bronze