Hệ thống mái che

Một dự án xây dựng cơ sở mới cho Trường PTNK gồm hai tòa nhà cao tầng. Trên bản vẽ, nhìn từ trên xuống, các tòa nhà có thể xem như các hình chữ nhật có cạnh song song với hệ trục tọa độ và không giao nhau. Mỗi hình chữ nhật được xác định bởi tọa độ góc trái dưới và góc phải trên. Hình thứ nhất có tọa độ góc trái dưới $(x_1,y_1)$ và góc phải trên $(x_2,y_2)$. Hình thứ hai có tọa độ góc trái dưới $(x_3,y_3)$ và góc phải trên $(x_4,y_4)$. Tọa độ đều là các số nguyên có giá trị tuyệt đối không vượt quá ${10}^6$.

Để tiện lợi cho việc đi lại giữa hai tòa nhà và tránh được mưa nắng, nhà trường đề nghị làm một đường mái che nối hai tòa nhà. Trên bản vẽ, đường mái che là một đoạn thẳng nối một điểm trên cạnh hình chữ nhật này đến một điểm trên cạnh của hình chữ nhật còn lại. Để tiết kiệm chi phí, nhà trường cần tìm phương án làm đường mái che sao cho độ dài của đoạn thẳng tương ứng là nhỏ nhất có thể.

Hai hình chữ nhật không giao nhau được hiểu là chúng không có điểm chung nào (kể cả điểm trên cạnh), và không hình nào nằm bên trong hình kia.

Yêu cầu: Cho trước $8$ giá trị $x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4$. Hãy tính bình phương độ dài ngắn nhất của đoạn cần làm mái che.

Dữ liệu vào

Một dòng chứa $8$ số nguyên $x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4$ có giá trị tuyệt đối không vượt quá ${10}^6$.

Dữ liệu ra

In ra một số nguyên là bình phương độ dài mái che tìm được.

Ràng buộc

• $|x_i|,|y_i|\le {10}^6$ với mọi $i$.
• $x_1<x_2$, $y_1<y_2$, $x_3<x_4$, $y_3<y_4$.
• Hai hình chữ nhật không có điểm chung.

Ví dụ