Hukum Moore menyatakan bahwa jumlah transistor pada sebuah cip akan berlipat dua setiap dua tahun. Menakjubkannya, hukum ini tetap berlaku selama lebih dari setengah abad. Setiap kali teknologi saat itu tidak lagi memungkinkan pertumbuhan, para peneliti menemukan teknologi manufaktur baru untuk mengemas rangkaian lebih rapat lagi. Dalam waktu dekat, hal ini mungkin berarti cip dibuat dalam tiga dimensi, bukan dua. Namun, untuk soal ini, dua dimensi sudah cukup.

Masalah yang umum dalam semua desain perangkat keras dua dimensi (misalnya cip, kartu grafis, papan induk, dan sebagainya) adalah penempatan kawat. Saat kawat dirutekan pada perangkat keras, masalah muncul jika kawat harus saling bersilangan. Ketika persilangan terjadi, perangkat khusus harus digunakan agar dua kawat listrik dapat melintas satu di atas yang lain, sehingga biaya produksi menjadi lebih mahal.

Masalah kita adalah sebagai berikut: Anda diberi desain perangkat keras dengan beberapa kawat yang sudah terpasang (semuanya berupa segmen garis lurus). Anda juga diberi titik awal dan akhir untuk sambungan kawat baru yang akan ditambahkan. Tentukan jumlah minimum kawat yang sudah ada yang harus dilintasi untuk menghubungkan titik awal dan akhir. Sambungan ini tidak harus berupa garis lurus. Satu-satunya syarat adalah sambungan tidak boleh melintas pada titik tempat dua atau lebih kawat yang sudah ada bertemu atau berpotongan.

Gambar L.1: Masukan contoh pertama.

Gambar L.1 menunjukkan masukan contoh pertama. Delapan kawat yang sudah ada membentuk lima persegi. Titik awal dan akhir sambungan baru masing-masing berada di persegi paling kiri dan paling kanan. Garis putus-putus hitam menunjukkan bahwa sambungan langsung akan melintasi empat kawat, sedangkan solusi optimal hanya melintasi dua kawat (garis lengkung biru).

Masukan

Masukan terdiri atas satu kasus uji. Baris pertama memuat lima bilangan bulat $m,x_0,y_0,x_1,y_1$, yang menyatakan jumlah kawat yang sudah ada ($m \le 100$) dan titik awal serta akhir yang perlu dihubungkan. Berikutnya terdapat $m$ baris, masing-masing memuat empat bilangan bulat $x_a,y_a,x_b,y_b$ yang menggambarkan kawat yang sudah ada dengan panjang bukan nol dari $(x_a,y_a)$ ke $(x_b,y_b)$. Nilai absolut setiap koordinat masukan kurang dari $10^5$. Setiap pasangan kawat memiliki paling banyak satu titik persekutuan, artinya kawat tidak saling tumpang tindih. Titik awal dan akhir kawat baru tidak terletak pada kawat yang sudah ada.

Keluaran

Tampilkan jumlah minimum kawat yang harus dilintasi untuk menghubungkan titik awal dan akhir.

Contoh

Masukan 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

Keluaran 1

2

Masukan 2

1 0 5 10 5
0 0 10 10

Keluaran 2

0