Das Moore’sche Gesetz besagt, dass sich die Anzahl der Transistoren auf einem Chip alle zwei Jahre verdoppelt. Erstaunlicherweise gilt dieses Gesetz seit mehr als einem halben Jahrhundert. Sobald die jeweilige Technologie kein weiteres Wachstum mehr zuließ, entwickelten Forscher neue Fertigungstechniken, um Schaltungen noch dichter zu packen. In naher Zukunft könnte dies bedeuten, Chips in drei statt zwei Dimensionen zu bauen. Für diese Aufgabe reichen jedoch zwei Dimensionen aus.

Ein gemeinsames Problem aller zweidimensionalen Hardwareentwürfe (beispielsweise Chips, Grafikkarten, Hauptplatinen usw.) ist die Platzierung von Drähten. Beim Verlegen von Drähten auf der Hardware ist es problematisch, wenn sie einander kreuzen müssen. Bei einer Kreuzung sind spezielle Vorrichtungen nötig, damit zwei elektrische Drähte übereinander hinweggeführt werden können. Dies verteuert die Herstellung.

Unsere Aufgabe lautet wie folgt: Gegeben ist ein Hardwareentwurf mit mehreren bereits platzierten Drähten (alles gerade Strecken). Außerdem sind Anfangs- und Endpunkt einer neu hinzuzufügenden Drahtverbindung gegeben. Bestimme die minimale Anzahl vorhandener Drähte, die gekreuzt werden müssen, um diese Punkte zu verbinden. Die Verbindung muss keine gerade Linie sein. Die einzige Bedingung ist, dass sie keinen Punkt kreuzen darf, an dem sich bereits zwei oder mehr Drähte treffen oder schneiden.

Abbildung L.1: Erste Beispieleingabe.

Abbildung L.1 zeigt die erste Beispieleingabe. Acht vorhandene Drähte bilden fünf Quadrate. Anfangs- und Endpunkt der neuen Verbindung liegen im ganz linken beziehungsweise ganz rechten Quadrat. Die schwarze gestrichelte Linie zeigt, dass eine direkte Verbindung vier Drähte kreuzen würde, während die optimale Lösung nur zwei Drähte kreuzt (die blaue Kurve).

Eingabe

Die Eingabe besteht aus einem einzigen Testfall. Die erste Zeile enthält fünf ganze Zahlen $m,x_0,y_0,x_1,y_1$, die die Anzahl vorhandener Drähte ($m \le 100$) und die zu verbindenden Anfangs- und Endpunkte angeben. Es folgen $m$ Zeilen mit jeweils vier ganzen Zahlen $x_a,y_a,x_b,y_b$, die einen vorhandenen Draht positiver Länge von $(x_a,y_a)$ nach $(x_b,y_b)$ beschreiben. Der Betrag jeder Eingabekoordinate ist kleiner als $10^5$. Jedes Drahtpaar hat höchstens einen gemeinsamen Punkt, die Drähte überlappen sich also nicht. Anfangs- und Endpunkt des neuen Drahts liegen auf keinem vorhandenen Draht.

Ausgabe

Gib die minimale Anzahl von Drähten aus, die gekreuzt werden müssen, um Anfangs- und Endpunkt zu verbinden.

Beispiele

Eingabe 1

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

Ausgabe 1

2

Eingabe 2

1 0 5 10 5
0 0 10 10

Ausgabe 2

0