Vectơ

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
kitsune
Dạng bài
Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(n\) vectơ trên hệ trục tọa độ Descartes, vectơ thứ \(i\) \((1 \leq i \leq n)\) có tọa độ \((x_{i}, y_{i})\). Hãy chọn một tập hợp các vectơ đã cho sao cho độ dài của tổng các vectơ là lớn nhất.

Input

  • Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 2 \times 10^{5})\).
  • Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_{i}\) và \(y_{i}\) \((|x_{i}|, |y_{i}| \leq 10^{4})\).

Output

  • Một dòng duy nhất chứa một số nguyên là bình phương độ dài lớn nhắt.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
  • Subtask \(2\) (\(40\%\) số điểm): \(n \leq 2 \times 10^{3}\).
  • Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
5
2 -2
-2 -2
0 2
3 1
-3 1
Output 
26
Note

Một phương án tối ưu là là chọn tập gồm các vectơ \((0, 2)\), \((3, 1)\) và \((2, -2)\).

Bình luận