도로

면접 대비

시간 제한2초메모리 제한1024 MB

요약

정수 격자 위의 단위 도로가 주어질 때, 시장의 집에서 시청까지 이동 거리를 가장 짧게 만드는 데 필요한 새 도로의 최소 개수를 구합니다.

난이도: 보통10점 중 4점
유형: 최단 경로, BFS, 그래프
정답자: 아직 제출이 없습니다

문제

뉴플레츠시티의 도로망은 아주 단순합니다. 모든 도로는 길이가 1인 선분이며, 양 끝점은 정수 좌표에 있습니다. 이 사실은 이 도시의 잘 알려진 특징 중 하나입니다.

최근 취임한 시장은 자신의 집과 시청 사이를 오가는 길에 너무 많은 시간을 쓴다고 생각합니다. 그래서 이 경로가 가능한 한 짧아지도록 새 도로를 몇 개 건설하기로 했습니다. 새 도로도 길이가 1인 선분이어야 하며, 양 끝점은 정수 좌표에 있어야 합니다.

뉴플레츠시티의 수석 엔지니어로서, 시장의 계획을 실행하는 데 건설해야 할 도로의 최소 개수를 구하십시오.

입력

첫 줄에 정수 $n$ ( $0 \le n \le 100$ )이 주어집니다. 이는 뉴플레츠시티의 도로 개수입니다. 이어지는 $n$ 개 줄에는 공백으로 구분된 정수 네 개 $x_i, y_i, x_j, y_j$ 가 주어집니다. 이는 각 도로의 시작점과 끝점 좌표입니다 ( $0 \le x_i, y_i, x_j, y_j \le 100$ ). 마지막 줄에는 시장 집의 좌표를 나타내는 정수 $m_x$ 와 $m_y$ 가 주어집니다 ( $0 \le m_x, m_y \le 100$ ). 시청은 $(0, 0)$ 에 있습니다.

모든 도로는 가로 또는 세로로 놓여 있고, 길이는 각각 1입니다. 도로는 양방향으로 통행할 수 있습니다.

출력

첫 줄에 뉴플레츠시티에 새로 건설해야 하는 도로의 개수 $M$ 을 출력합니다.

예제2

예제 1
입력
```
1
0 0 1 0
1 1
```
예상 출력
```
1
```

예제 2

입력

예상 출력