VOI 20 Bài 5 - Tòa nhà - VNOJ: VNOI Online Judge

VOI 20 Bài 5 - Tòa nhà

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.12s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Kỳ thi Học sinh giỏi Quốc gia 2020 - Ngày 2

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Đọc đề gốc tại đây.

Thành phố nơi Alice sinh sống có ~n~ toà nhà. Trên bản thiết kế, mặt bằng nền mỗi tòa nhà đều là hình chữ nhật có các cạnh song song với trục tọa độ, với các đỉnh đều có tọa độ nguyên trên hệ trục tọa độ. Hai tòa nhà gọi là liền kề nếu có hai đường biên của hai hình chữ nhật mặt nền tương ứng hai tòa nhà đó có ít nhất một điểm chung. Để thuận tiện đi lại giữa các tòa nhà, người ta xây dựng một lối đi tắt hai chiều giữa mỗi cặp tòa nhà liền kề.

Alice rất thích thú với cách thiết kế các tòa nhà của thành phố và thường xuyên đi lại giữa các tòa nhà thông qua các lối đi tắt này. Sau một thời gian khám phá, Alice nhận thấy có một số lối đi tắt là độc đạo. Một lối đi tắt giữa hai tòa nhà ~u~ và ~v~ gọi là độc đạo nếu như sau khi đi từ ~u~ sang ~v~ qua lối đi này thì không có cách đi nào quay trở lại ~u~ thông qua các lối đi tắt khác ngoài lối đi tắt từ ~v~ về ~u~.

Với mỗi cặp tòa nhà ~(u, v)~ có lối đi tắt là độc đạo, Alice tiếp tục khám phá nếu như đóng cửa lối đi độc đạo này thì xuất phát từ ~u~ Alice có thể tham quan được tối đa ~d_u~ tòa nhà, và nếu xuất phát từ ~v~ Alice có thể tham quan được tối đa ~d_v~ tòa nhà. Khoảng chênh lệch giữa ~d_u~ và ~d_v~ là giá trị ~|d_u - d_v|~.

Yêu cầu: Biết tọa độ các đỉnh hình chữ nhật mặt nền tương ứng của các tòa nhà, hãy giúp Alice tìm cặp tòa nhà ~(u, v)~ có lối đi tắt độc đạo sao cho khoảng chênh lệch giữa ~d_u~ và ~d_v~ là nhỏ nhất.

Input

Dòng thứ nhất chứa một số nguyên dương ~n~ là số lượng tòa nhà cao tầng;
Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ~4~ số nguyên không âm ~x_i, y_i, p_i, q_i~ với ~(x_i, y_i)~ là tọa độ của đỉnh trái trên và ~(p_i, q_i)~ là tọa độ của đỉnh phải dưới của hình chữ nhật biểu thị mặt nền tòa nhà thứ ~i~ trên bản đồ quy hoạch. Dữ liệu đảm bảo ~x_i < p_i~ và ~y_i > q_i~ và hai hình chữ nhật bất kỳ có thể tiếp xúc nhưng không giao nhau.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra một số nguyên duy nhất là khoảng chênh lệch nhỏ nhất tìm được. Nếu không tồn tại lối đi tắt độc đạo thì in ra số ~-1~.

Giới hạn

Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 10^3~, các tọa độ không vượt quá ~10^9~;
~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 10^5~, các tọa độ không vượt quá ~10^3~;
~40\%~ số test còn lại ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 10^5~, các tọa độ không vượt quá ~10^9~.

Sample Input

Sample Output

Note

Có ~2~ lối đi độc đạo là lối đi giữa cặp tòa nhà ~(4, 5)~ và ~(5, 6)~. Nếu đóng cửa lối đi độc đạo qua ~(4, 5)~, ta có ~d_4 = 4~ và ~d_5 = 2~, do đó ~|d_4 - d_5| = 2~. Nếu đóng cửa lối đi độc đạo qua ~(5, 6)~, ta có ~d_5 = 5~ và ~d_6 = 1~, do đó ~|d_5 - d_6| = 4~.

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.