울타리

농장에 철조망으로 울타리를 만들었다고 한다. 울타리는 단위 철조망들로 구성되는데, 한 단위 철조망은 두개의 말뚝을 똑바른 선분 모양의 철조망으로 이은 것이다. N개의 단위 철조망이 2차원 평면 상의 좌표로 주어진다. 두 단위 철조망이 중간에서 만나는 경우는 없고, 두 단위 철조망이 점을 공유한다면 한 말뚝만 공유가 가능하다.

울타리나 말뚝 위에 있지 않은 두 점 $S$와 $T$가 주어진다고 하자. $S$에서 $T$로 임의의 곡선을 통해서 이동하면 울타리 위의 점을 지나는 개수를 알 수 있을 것이다. 단, 곡선이 말뚝 위를 지날 수 없다.

아래 그림에서 똑바른 선분들은 울타리들이다. $S$와 $T$의 위치가 표시되어 있다. 세 개의 곡선이 그려져 있는데, 그 중 울타리 위의 점을 지나는 개수가 가장 작은 것은 위쪽 곡선이며 $0$개의 점을 지난다.

울타리의 모양과 $S$, $T$의 위치를 입력으로 받아 $S$와 $T$를 연결하는 곡선들 중 울타리 위의 점을 지나는 개수가 가장 작은 것을 찾는 프로그램을 작성하라.

입력 형식

첫째 줄에는 단위 철조망의 개수 $N$이 주어진다. ($1 \le N \le 100\,000$)

다음 $N$개의 줄에 단위 철조망이 $X_1$, $Y_1$, $X_2$, $Y_2$의 $4$개의 정수로 주어진다. 서로 다른 위치 $(X_1, Y_1)$과 $(X_2, Y_2)$에 있는 말뚝을 잇는 단위 철조망이라는 의미이다.

다음 $1$개의 줄에 $S$와 $T$의 좌표가 각각 공백으로 구분되어 주어진다. 모든 좌표 값은 $-10^9$에서 $10^9$까지의 정수이다.

출력 형식

첫째 줄에 울타리 위의 점을 지나는 가장 작은 개수를 출력한다.

예제 1

3
1 1 5 1
1 1 1 5
5 1 5 5
3 3 8 3

0

예제 2

8
1 1 7 1
7 1 7 7
7 7 1 7
1 7 1 1
2 2 6 2
6 2 6 6
6 6 2 6
2 6 2 2
4 4 9 4

2

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설