Bessie từng có một khung cảnh thật đẹp nhìn từ chuồng bò của mình, qua con đường về phía hai tấm biển quảng cáo thức ăn cho bò trông rất ngon. Không may, một trong hai tấm biển gần đây đã được thay nội dung thành quảng cáo cho “Máy cắt cỏ của bác nông dân Larry”. Bessie không thích máy cắt cỏ, bởi theo những gì cô biết, mục đích duy nhất của chúng là cắt ngắn đám cỏ thơm ngon trong cánh đồng của cô (nếu bạn chưa nhận ra, phần lớn suy nghĩ của Bessie đều xoay quanh thức ăn).

May mắn thay, tấm biển quảng cáo thức ăn cho bò còn lại nằm phía trước tấm biển quảng cáo máy cắt cỏ và có thể che khuất nó.

Quyết tâm loại bỏ hoàn toàn tấm biển quảng cáo máy cắt cỏ đáng ghét khỏi tầm mắt, Bessie nghĩ ra một kế hoạch mạo hiểm. Cô định lấy trộm một tấm bạt hình chữ nhật lớn trong chuồng bò rồi lẻn ra ngoài vào đêm khuya để che phần còn lại của tấm biển quảng cáo máy cắt cỏ, sao cho cô không còn nhìn thấy bất kỳ phần nào của nó.

Cho vị trí của hai tấm biển quảng cáo, hãy giúp Bessie tính diện tích nhỏ nhất của tấm bạt mà cô cần. Vì trong chuồng chỉ có các tấm bạt hình chữ nhật, Bessie nhận thấy cô có thể cần một tấm bạt có diện tích lớn hơn một chút so với phần lộ ra của tấm biển quảng cáo máy cắt cỏ, như trong ví dụ bên dưới. Chỉ được đặt tấm bạt sao cho các cạnh của nó song song với các cạnh của hai tấm biển (nghĩa là không được đặt “nghiêng”).

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên cách nhau bởi dấu cách: \(x_1\) \(y_1\) \(x_2\) \(y_2\), trong đó \((x_1, y_1)\) và \((x_2, y_2)\) lần lượt là tọa độ góc dưới bên trái và góc trên bên phải của tấm biển quảng cáo máy cắt cỏ trong trường nhìn hai chiều của Bessie. Dòng tiếp theo chứa thêm bốn số nguyên, tương tự mô tả góc dưới bên trái và góc trên bên phải của tấm biển quảng cáo thức ăn cho bò. Tấm biển quảng cáo thức ăn cho bò có thể che toàn bộ, một phần hoặc không che phần nào của tấm biển quảng cáo máy cắt cỏ. Mọi tọa độ đều nằm trong khoảng từ \(-1000\) đến \(+1000\).

Dữ liệu ra

In ra diện tích nhỏ nhất của tấm bạt Bessie cần dùng để che một phần tấm biển quảng cáo máy cắt cỏ sao cho nó bị che khuất hoàn toàn.

Ví dụ

2 1 7 4
5 -1 10 3

15

Nguồn

USACO 2018 January Contest, Bronze — Blocked Billboard II

Tác giả bài toán: Brian Dean.