Định luật Moore phát biểu rằng số bóng bán dẫn trên một con chip tăng gấp đôi sau mỗi hai năm. Thật đáng kinh ngạc, định luật này đã đúng suốt hơn nửa thế kỷ. Mỗi khi công nghệ hiện tại không còn cho phép tăng trưởng thêm, các nhà nghiên cứu lại tìm ra công nghệ chế tạo mới để bố trí mạch với mật độ cao hơn nữa. Trong tương lai gần, điều này có thể có nghĩa là chip được chế tạo trong không gian ba chiều thay vì hai chiều. Nhưng với bài toán này, hai chiều là đủ.

Một vấn đề chung của mọi thiết kế phần cứng hai chiều (chẳng hạn chip, card đồ họa, bo mạch chủ, v.v.) là bố trí dây dẫn. Khi đi dây trên phần cứng, việc các dây phải cắt nhau gây ra khó khăn. Khi có giao cắt, phải dùng các thiết bị đặc biệt để hai dây điện có thể đi qua phía trên nhau, khiến chi phí chế tạo tăng lên.

Bài toán của chúng ta như sau: bạn được cho một thiết kế phần cứng với một số dây đã được bố trí sẵn (tất cả đều là đoạn thẳng). Bạn cũng được cho điểm đầu và điểm cuối của một kết nối dây mới cần thêm vào. Bạn phải xác định số dây hiện có ít nhất cần đi cắt qua để nối điểm đầu và điểm cuối. Kết nối này không nhất thiết là đường thẳng. Yêu cầu duy nhất là nó không được đi cắt qua tại một điểm mà hai dây hiện có trở lên đã gặp hoặc giao nhau.

Hình L.1: Dữ liệu vào ví dụ thứ nhất.

Hình L.1 minh họa dữ liệu vào ví dụ thứ nhất. Tám dây hiện có tạo thành năm hình vuông. Điểm đầu và điểm cuối của kết nối mới lần lượt nằm trong hình vuông ngoài cùng bên trái và ngoài cùng bên phải. Đường đứt nét màu đen cho thấy nối trực tiếp sẽ cắt qua bốn dây, trong khi lời giải tối ưu chỉ cắt qua hai dây (đường cong màu xanh lam).

Dữ liệu vào

Dữ liệu vào gồm một bộ kiểm thử duy nhất. Dòng đầu tiên chứa năm số nguyên $m,x_0,y_0,x_1,y_1$, là số dây hiện có ($m \le 100$) và điểm đầu, điểm cuối cần nối. Tiếp theo là $m$ dòng, mỗi dòng chứa bốn số nguyên $x_a,y_a,x_b,y_b$ mô tả một dây hiện có có độ dài khác không từ $(x_a,y_a)$ đến $(x_b,y_b)$. Giá trị tuyệt đối của mỗi tọa độ đầu vào nhỏ hơn $10^5$. Mỗi cặp dây có nhiều nhất một điểm chung, nghĩa là các dây không chồng lên nhau. Điểm đầu và điểm cuối của dây mới không nằm trên dây hiện có nào.

Dữ liệu ra

In ra số dây ít nhất phải đi cắt qua để nối điểm đầu và điểm cuối.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

2

Dữ liệu vào 2

1 0 5 10 5
0 0 10 10

Dữ liệu ra 2

0