레이팅 미적용매일 농부 존(Farmer John)의 N마리 (1 <= N <= 100,000) 소들은 농장 한가운데의 도로를 건넌다. FJ의 농장 지도를 2차원 평면으로 생각하면, 도로는 수평으로 나 있으며 도로의 한쪽은 직선 y=0으로, 다른 쪽은 y=1로 표현된다. 소 i는 한쪽의 위치 (a_i, 0)에서 반대쪽의 위치 (b_i, 1)까지 직선 경로를 따라 도로를 건넌다. 모든 a_i는 서로 다르고 모든 b_i도 서로 다르며, 이 수들은 모두 -1,000,000...1,000,000 범위의 정수이다.
소들이 비교적 날렵하기는 하지만, FJ는 경로가 교차하는 소 쌍이 건너는 도중 충돌하여 서로 다칠까 봐 자주 걱정한다. FJ는 다른 어떤 소의 경로도 자신의 경로와 교차하지 않는 소를 "안전하다"고 여긴다. 안전한 소의 수를 계산하는 것을 FJ에게 도와주자.
첫째 줄: 소의 수 N.
둘째 줄부터 1+N번째 줄까지: i번째 줄에 소 i가 지나는 경로를 나타내는 정수 a_i와 b_i가 주어진다.
안전한 소의 수.
crossings.in · 출력을 쓸 파일 crossings.out4
-3 4
7 8
10 16
3 92Output details: The first and third cows do not intersect any other cows. The second and fourth cows intersect each other.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > February > Bronze