Có thể các bạn chưa biết, nhưng ở hầu hết các vị giáo sư, ngoài sở thích sưu tầm những câu chuyện cười, đố vui hay các trò chơi lý thú để phục vụ những giờ lên lớp, họ còn rất yêu thích trồng hoa và cây cảnh. Ngôi nhà của những vị giáo sư, vì thế, luôn là nơi tụ hội của những nàng hoa xinh xắn và quyến rũ, từ nàng hồng kiêu sa, nàng cúc vàng tươi đến nàng dạ lý thơm ngát.
Khu vườn của GS. PVH có cây hoa. Nếu coi khu vườn như hệ trục tọa độ Descartes, cây hoa thứ được trồng ở điểm có tọa độ . Ban đầu, vị giáo sư muốn trồng hoa ở khắp khu vườn, để hương thơm ngào ngạt có thể lan tỏa khắp muôn nơi. Nhưng rồi, số lượng hoa quá lớn khiến việc chăm sóc hoa gặp nhiều khó khăn. Do đó, giáo sư cần phải quy hoạch lại vườn hoa của mình.
GS. PVH quyết định sẽ di chuyển cây hoa về hai trục tọa độ và từ nay chỉ trồng hoa trên đó. Để việc di chuyển được đơn giản, các cây hoa chỉ được di chuyển song song theo một trong hai trục tọa độ. Nói cách khác, nếu ban đầu một cây hoa đang ở vị trí , nó sẽ chỉ được chuyển về một trong hai vị trí hoặc .
Chuyển đổi từ chiến thuật “phân bố rải rác” sang “canh tác tập trung”, vị giáo sư muốn sau khi quy hoạch lại vườn hoa, khoảng cách giữa hai cây hoa xa nhau nhất là nhỏ nhất có thể. Việc lấy thước đo khoảng cách hẳn sẽ tốn rất nhiều mồ hôi và nước mắt, giáo sư muốn bạn tìm ra giá trị tối thiểu này.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên dương , số cây hoa trong vườn.
dòng tiếp theo, dòng thứ chứa hai số nguyên và , là tọa độ ban đầu của cây hoa thứ .
Dữ liệu ra:
Gồm một số duy nhất là bình phương khoảng cách tối thiểu có thể đạt được giữa hai cây hoa xa nhau nhất. Dễ dàng thấy được đây là một số nguyên.
Ví dụ:
Dữ liệu vào:
3
22 2
7 -1
1 97
Dữ liệu ra:
9
Giải thích:
Có cây hoa ở các vị trí , và . Di chuyển chúng về các điểm và . Khi đó khoảng cách giữa hai cây xa nhất là (giữa cây và ). Đây là giá trị nhỏ nhất có thể đạt được của khoảng cách giữa hai cây xa nhất.
Chú ý ta cần in ra bình phương của khoảng cách tối thiểu.
Dữ liệu vào:
2
1 100
2 100
Dữ liệu ra:
0
Giải thích:
Di chuyển cả cây về cùng vị trí . Khoảng cách giữa cây khi đó là .
