ARCHI - Khảo cổ
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

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 toạ độ Đề các vuông góc Oxy 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ó n bức tường được đánh số từ 1 đến n. Bức tường thứ i là đoạn thẳng nối từ điểm có tọa độ nguyên (xi, yi) đến điểm có tọa độ nguyên (ui, vi), i = 1, 2, …, n. Hai đoạn thẳng mô tả hai bức tườ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:

- Bướ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;
- Bước 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 đồ;
- Bước 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, 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ả các bức tường của Hoàng Thành.

Input

- Dòng đầu là số nguyên n (n ≤ 1000) là số lượng bức tường;
- Dòng thứ i trong số n dòng tiếp theo chứa 4 số nguyên xi, yi, ui, vi được ghi cách nhau bởi dấu cách (|xi|, |yi|, |ui|, |vi| ≤ 1000) là các tọa độ của hai đầu mút của đoạn thẳng mô tả bức tường thứ i (i = 1, 2, …, n).

Output

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

Ví dụ

Input

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

Output

2

 


Nguồn: 3D 20162017

Back to Top