레이팅 미적용무어의 법칙은 칩의 트랜지스터 수가 2년마다 두 배가 된다고 말한다. 놀랍게도 이 법칙은 반세기가 넘도록 유효했다. 현재 기술로 더 이상 성장이 불가능해질 때마다 연구자들은 회로를 더 조밀하게 채우는 새로운 제조 기술을 내놓았다. 가까운 미래에는 칩이 2차원이 아니라 3차원으로 만들어질 수도 있다. 하지만 이 문제에서는 2차원이면 충분하다. 모든 2차원(t\(wo-di\)mensional) 하드웨어 설계(예를 들어 칩, 그래픽 카드, 메인보드(mo\(th- er\)boards) 등)에 공통된 문제는 전선 배치이다. 하드웨어에 전선을 배선할 때 전선들이 서로 교차해야 하면 문제가 된다. 교차가 발생하면 두 전선이 서로를 넘어가도록 특수 장치를 써야 하고, 이는 제조 비용을 높인다. 우리의 문제는 다음과 같다. 여러 전선이 이미 배치된(모두 직선 선분인) 하드웨어 설계가 주어진다. 또한 새로 추가할 전선 연결의 시작점과 끝점이 주어진다. 시작점과 끝점을 연결하기 위해 교차해야 하는 기존 전선의 최소 개수를 구해야 한다. 이 연결은 직선일 필요가 없다. 유일한 요구 사항은 이미 두 개 이상의 전선이 만나거나 교차하는 지점에서는 교차할 수 없다는 것이다. 그림 L.1: 첫 번째 샘플 입력 그림 L.1은 첫 번째 샘플 입력을 보여 준다. 기존 전선 여덟 개가 정사각형 다섯 개를 이룬다. 새 연결의 시작점과 끝점은 각각 맨 왼쪽과 맨 오른쪽 정사각형 안에 있다. 검은 파선은 직선 연결이 전선 네 개를 교차함을 보여 주고, 최적해는 전선 두 개만 교차한다(굽은 파란 선).
입력은 하나의 테스트 케이스로 이루어져 있다. 첫 줄에는 다섯 정수 m, x0, y0, x1, y1이 주어지며, 이는 기존(p\(re-ex\)isting) 전선의 수(\(m \le 100\))와 연결해야 할 시작점, 끝점이다. 이어서 \(m\)개의 줄에 각각 네 정수 \(x_{a}\), y_{a}, x_{b}, y_{b}가 주어지며, 이는 (\(xa\), y\(a\))에서 (\(x_{b}\), y_{b})까지 길이가 0이 아닌(n\(on-ze\)ro) 기존 전선을 설명한다. 각 입력 좌표의 절댓값은 \(10^{5}\)보다 작다. 어떤 전선 쌍도 공통점을 최대 하나만 가진다. 즉, 전선들은 겹치지 않는다. 새 전선의 시작점과 끝점은 기존(p\(re-ex\)isting) 전선 위에 있지 않다.
시작점과 끝점을 연결하기 위해 교차해야 하는 전선의 최소 개수를 출력한다.
8 3 3 19 3
0 1 22 1
0 5 22 5
1 0 1 6
5 0 5 6
9 0 9 6
13 0 13 6
17 0 17 6
21 0 21 6
21 0 5 10 5
0 0 10 10
0