VOMOVREC - Di chuyển hình chữ nhật

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274861/problem/I
https://codeforces.com/group/FLVn1Sc504/contest/271722/problem/A

Cho N hình chữ nhật trên mặt phẳng Oxy. Các hình chữ nhật này có toạ độ nguyên và có các cạnh song song với trục toạ độ. Ở mỗi lượt, các hình chữ nhật có thể đứng yên hoặc di chuyển theo 8 hướng:

  • sang trái 1 đơn vị
  • sang phải 1 đơn vị
  • lên trên 1 đơn vị
  • xuống dưới 1 đơn vị
  • sang trái và lên trên 1 đơn vị
  • sang trái và xuống dưới 1 đơn vị
  • sang phải và lên trên 1 đơn vị
  • sang phải và xuống dưới 1 đơn vị

Hãy xác định sau ít nhất bao nhiên lượt thì N hình chữ nhật ban đầu sẽ được di chuyển đến các vị trí mới sao cho phần diện tích giao nhau của tất cả N hình chữ nhật này lớn hơn hoặc bằng 1.

Dữ liệu vào

Dòng đầu tiên ghi số N là số lượng các hình chữ nhật.

Tiếp theo là N dòng, mỗi dòng ghi 4 số nguyên x 1 , y 1 , x 2 , y 2 thể hiện hình chữ nhật có góc trái dưới là ( x 1 , y 1 ) góc phải trên là ( x 2 , y 2 ).

Dữ liệu ra

In ra số lượt di chuyển tối thiểu.

Giới hạn

Subtask 1 (30% số điểm)

  • 2 ≤ N ≤ 200
  • |tọa độ| ≤ 100
  • Chỉ gồm các hình vuông đơn vị với cạnh là 1

Subtask 2 (40% số điểm)

  • 200 < N ≤ 10 5
  • |toạ độ| ≤ 2 * 10 9
  • Chỉ gồm các hình vuông đơn vị với cạnh là 1

Subtask 3 (30% số điểm)

  • 200 < N ≤ 10 5
  • |tọa độ| ≤ 2 * 10 9

Ví dụ 

Input:
3
0 0 1 1
0 0 2 3
2 3 4 5
Output:
2

Giải thích

Sau 2 lượt:

  • Hình 1: Di chuyển lên trên 1 đơn vị rồi sau đó di chuyển chéo lên phải 1 đơn vị.
  • Hình 2: Đứng yên.
  • Hình 3: Di chuyển chéo xuống trái 1 đơn vị.

  • Người up: voj
  • Nguồn bài: VNOI Online 2016