กฎของ Moore กล่าวว่า จำนวนทรานซิสเตอร์บนชิปจะเพิ่มเป็นสองเท่าทุกสองปี น่าอัศจรรย์ที่กฎนี้ยังคงเป็นจริงมาแล้วกว่าครึ่งศตวรรษ เมื่อใดก็ตามที่เทคโนโลยีในขณะนั้นไม่อาจเพิ่มจำนวนได้อีก นักวิจัยก็คิดค้นเทคโนโลยีการผลิตใหม่เพื่อบรรจุวงจรให้หนาแน่นยิ่งขึ้น ในอนาคตอันใกล้ นี่อาจหมายถึงการสร้างชิปในสามมิติแทนสองมิติ แต่สำหรับโจทย์นี้ สองมิติก็เพียงพอแล้ว

ปัญหาที่พบร่วมกันในการออกแบบฮาร์ดแวร์สองมิติทุกประเภท (เช่น ชิป การ์ดกราฟิก เมนบอร์ด เป็นต้น) คือการวางสายไฟ ขณะเดินสายไฟบนฮาร์ดแวร์ หากสายไฟต้องตัดกันก็จะเป็นปัญหา เมื่อเกิดการตัดกัน ต้องใช้อุปกรณ์พิเศษเพื่อให้สายไฟสองเส้นผ่านข้ามกันได้ ซึ่งทำให้การผลิตมีต้นทุนสูงขึ้น

ปัญหาของเรามีดังนี้: คุณได้รับแบบฮาร์ดแวร์ที่มีสายไฟวางอยู่แล้วหลายเส้น (ทั้งหมดเป็นส่วนของเส้นตรง) และได้รับจุดเริ่มต้นกับจุดสิ้นสุดของสายเชื่อมต่อใหม่ที่จะเพิ่มเข้าไป คุณต้องหาจำนวนสายไฟเดิมน้อยที่สุดที่จำเป็นต้องตัดผ่านเพื่อเชื่อมจุดเริ่มต้นกับจุดสิ้นสุด เส้นเชื่อมต่อนี้ไม่จำเป็นต้องเป็นเส้นตรง ข้อกำหนดเพียงอย่างเดียวคือห้ามตัดผ่าน ณ จุดที่มีสายไฟเดิมตั้งแต่สองเส้นขึ้นไปมาบรรจบหรือตัดกันอยู่แล้ว

รูป L.1: ข้อมูลนำเข้าตัวอย่างแรก

รูป L.1 แสดงข้อมูลนำเข้าตัวอย่างแรก สายไฟเดิมแปดเส้นประกอบเป็นสี่เหลี่ยมจัตุรัสห้ารูป จุดเริ่มต้นและจุดสิ้นสุดของเส้นเชื่อมต่อใหม่อยู่ในสี่เหลี่ยมซ้ายสุดและขวาสุดตามลำดับ เส้นประสีดำแสดงว่าการเชื่อมโดยตรงจะตัดผ่านสายไฟสี่เส้น ในขณะที่คำตอบที่ดีที่สุดตัดผ่านเพียงสองเส้น (เส้นโค้งสีน้ำเงิน)

ข้อมูลนำเข้า

ข้อมูลนำเข้ามีกรณีทดสอบเดียว บรรทัดแรกมีจำนวนเต็มห้าจำนวน $m,x_0,y_0,x_1,y_1$ ซึ่งระบุจำนวนสายไฟเดิม ($m \le 100$) และจุดเริ่มต้นกับจุดสิ้นสุดที่ต้องเชื่อม ถัดมามี $m$ บรรทัด แต่ละบรรทัดมีจำนวนเต็มสี่จำนวน $x_a,y_a,x_b,y_b$ อธิบายสายไฟเดิมที่มีความยาวไม่เป็นศูนย์จาก $(x_a,y_a)$ ถึง $(x_b,y_b)$ ค่าสัมบูรณ์ของแต่ละพิกัดในข้อมูลนำเข้าน้อยกว่า $10^5$ สายไฟแต่ละคู่มีจุดร่วมกันได้ไม่เกินหนึ่งจุด กล่าวคือสายไฟไม่ทับซ้อนกัน จุดเริ่มต้นและจุดสิ้นสุดของสายใหม่ไม่อยู่บนสายไฟเดิมใด ๆ

ข้อมูลส่งออก

แสดงจำนวนสายไฟน้อยที่สุดที่จำเป็นต้องตัดผ่านเพื่อเชื่อมจุดเริ่มต้นกับจุดสิ้นสุด

ตัวอย่าง

ข้อมูลนำเข้า 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

ข้อมูลส่งออก 1

2

ข้อมูลนำเข้า 2

1 0 5 10 5
0 0 10 10

ข้อมูลส่งออก 2

0