울타리

NYPC 2018 · 본선

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

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

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

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

입력 형식

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

다음 NN개의 줄에 단위 철조망이 X1X_1, Y1Y_1, X2X_2, Y2Y_244개의 정수로 주어진다. 서로 다른 위치 (X1,Y1)(X_1, Y_1)(X2,Y2)(X_2, Y_2)에 있는 말뚝을 잇는 단위 철조망이라는 의미이다.

다음 11개의 줄에 SSTT의 좌표가 각각 공백으로 구분되어 주어진다. 모든 좌표 값은 109-10^9에서 10910^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

채점 방식

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

종류 1: 27

모든 말뚝은 각 22개의 철조망에 연결되어 있다.

종류 2: 42

모든 말뚝의 쌍은 00개 이상의 철조망을 따라 가면 연결이 되어 있다.

종류 3: 31

별다른 제약조건 없음.

해설