레이팅 미적용농부 존(Farmer John)에게 차세대 인기 관람 스포츠에 대한 기막힌 아이디어가 떠올랐다. 바로 소 장애물 경마다! 모두가 알다시피, 일반적인 장애물 경마는 말들이 뛰어넘어야 하는 장애물로 가득한 경주로를 도는 경기이다. FJ는 장애물을 충분히 낮게만 만들면 고도로 훈련된 소들로도 같은 경기가 가능하리라 생각한다.
경주로를 설계하기 위해, FJ는 자신이 지을 수 있는 N개 (1 <= N <= 250)의 모든 장애물 후보를 그림으로 그렸다. 각 장애물은 2차원 평면에서 가로축 또는 세로축에 평행한 선분으로 표현된다. 장애물 i는 서로 다른 두 끝점 (X1_i, Y1_i)와 (X2_i, Y2_i) (1 <= X1_i, Y1_i, X2_i, Y2_i <= 1,000,000,000)를 가진다.
FJ는 어떤 두 장애물도 서로 교차하지 않는다는 조건 아래, 가능한 한 많은 장애물을 짓고 싶어 한다. 두 선분이 공통점을 하나라도 가지면(한쪽 또는 양쪽 선분의 끝점이라도) 교차한다고 한다. FJ는 원래 입력 그림에서 어떤 두 가로 선분도 교차하지 않고, 마찬가지로 어떤 두 세로 선분도 교차하지 않는다고 확신한다.
FJ가 지을 수 있는 장애물의 최대 개수를 구하는 것을 도와주자.
첫째 줄: 정수 N.
둘째 줄부터 N+1번째 줄까지: i+1번째 줄에 장애물을 나타내는, 공백으로 구분된 네 정수 X1_i, Y1_i, X2_i, Y2_i가 주어진다.
FJ가 고를 수 있는, 서로 교차하지 않는 선분의 최대 개수.
steeple.in · 출력을 쓸 파일 steeple.out3
4 5 10 5
6 2 6 12
8 3 8 52Input details: There are three potential obstacles. The first is a horizontal segment connecting (4, 5) to (10, 5); the second and third are vertical segments connecting (6, 2) to (6, 12) and (8, 3) to (8, 5).
Output details: The optimal solution is to choose both vertical segments.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > November > Gold