C. ARCHI - Khảo cổ

Các nhà khảo cổ mới phát hiện ra một khu Hoàng Thành được xây dựng từ nhiều thế kỷ trước. Theo nhận định ban đầu, Hoàng Thành gồm nhiều bức tường song song hoặc vuông góc với nhau. Để tiến hành nghiên cứu, các nhà khảo cổ đã xây dựng bản đồ các bức tường của khu Hoàng Thành. Cụ thể, bản đồ được mô tả trên mặt phẳng tọa độ Descartes vuông góc trong đó các bức tường là các đoạn thẳng song song với một trong hai trục tọa độ.

Theo các dữ liệu thu thập được, có bức tường được đánh số từ đến . bức tường thứ là đoạn thẳng nối từ điểm có tọa độ () đến điểm có tọa độ (), . Hai đoạn thẳng khác nhau có không quá một điểm chung.

Để in bản đồ, các nhà khảo cổ dùng một máy vẽ chuyên dụng hoạt động theo nguyên tắc:

1. Chọn một điểm có tọa độ nguyên, bút vẽ của máy vẽ được kích hoạt để di chuyển và hạ đầu bút xuống điểm này.
2. Bút vẽ di chuyển liên tục song song với một trong hai trục để vẽ các đoạn thẳng mô tả các bức tường trong bản đồ.
3. Nếu đã vẽ xong toàn bộ các bức tường thì kết thúc công việc, trong trường hợp ngược lại, máy sẽ quay về Bước 1 để tiếp tục thực hiện việc vẽ.

Hoạt động của máy vẽ được tối ưu hóa sao cho không có đoạn nào được vẽ quá một lần và số lần kích hoạt bút vẽ là ít nhất.

Yêu cầu: Cho biết các đoạn thẳng mô tả các bức tường, hãy tính số lần kích hoạt bút vẽ ít nhất để vẽ được bản đồ mô tả tất cả các bức tường của Hoàng Thành.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên là số lượng bức tường.
• Dòng thứ trong số dòng tiếp theo chứa số nguyên được ghi cách nhau bởi dấu cách là tọa độ của hai đầu mút của đoạn thẳng mô tả bức tường thứ .

Kết quả:

• Ghi số nguyên là số lần kích hoạt bút vẽ ít nhất.

Ví dụ:

Dữ liệu:

6
2 1 2 4
2 4 6 4
6 4 6 1
6 1 2 1
4 -1 4 6
3 2 5 2

Kết quả:

2

Giải thích:

Giới hạn:

• .
• Giá trị tuyệt đối của các tọa độ không vượt quá .