Đường Kính Tập Điểm

Buổi 61 — Hình học tính toán
Points
46
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho $N$ điểm trên mặt phẳng tọa độ. Hãy tìm bình phương khoảng cách Euclid lớn nhất giữa hai điểm bất kỳ trong $N$ điểm đó (tức bình phương đường kính của tập điểm).

Gợi ý: Tìm bao lồi bằng thuật toán Andrew rồi dùng kẹp quay (Rotating Calipers) trong $O(N \log N)$.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ ($2 \le N \le 10^5$).
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i, y_i$ ($|x_i|, |y_i| \le 10^9$).
Dữ liệu ra
  • In ra một số nguyên là bình phương khoảng cách lớn nhất giữa hai điểm bất kỳ.
Ví dụ
Input Output
4
0 0
3 0
0 4
1 1
25
Giới hạn
  • $2 \le N \le 10^5$
  • $|x_i|, |y_i| \le 10^9$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved