Chọn ĐTQG Đồng Nai 2026 - Lễ hội ánh sáng

Xem dạng PDF

Gửi bài giải

Điểm: 30,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Trung tâm tổ chức sự kiện ABC đang chuẩn bị một lễ hội ánh sáng tại quảng trường trung tâm. Trên bản thiết kế có ~n~ cột đèn đã được lắp tại ~n~ vị trí phân biệt, mỗi vị trí được biểu diễn bởi một điểm có tọa độ nguyên ~(x_i,y_i)~ trên mặt phẳng. Ban tổ chức muốn toàn bộ hệ thống đèn có tâm đối xứng, nghĩa là tồn tại một điểm ~O~ sao cho với mỗi cột đèn tại vị trí ~A~, vị trí đối xứng của ~A~ qua ~O~ cũng có một cột đèn. Điểm ~O~ có thể trùng với vị trí của một cột đèn đã có hoặc là một vị trí không có cột đèn. Các cột đèn đã lắp không thể di chuyển, nhưng có thể lắp thêm cột đèn tại những vị trí mới, tọa độ của các vị trí được bổ sung không bắt buộc phải là số nguyên mà có thể là số thực. Hãy xác định số cột đèn ít nhất cần lắp thêm để hệ thống đèn thu được có tâm đối xứng.

Input

  • Dòng đầu chứa số nguyên ~n~ ~(2 \le n \le 1000)~ là số cột đèn đã được lắp;

  • ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i, y_i~ là tọa độ vị trí của cột đèn thứ ~i~ ~(-20000 \le x_i,y_i \le 20000)~.

Output

Một số nguyên duy nhất là số cột đèn ít nhất cần lắp thêm.

Scoring

Subtask Điểm Ràng buộc
1 ~40\%~ ~n \le 20~
2 ~30\%~ ~n \le 200~
3 ~30\%~ Không có giới hạn gì thêm

Sample Input 1

2
0 0
2 2

Sample Output 1

0

Sample Input 2

6
0 0
4 0
0 4
4 4
1 1
1 2

Sample Output 2

2

Notes

Test 1: Hai điểm ~(0,0)~ và ~(2,2)~ có tâm đối xứng là điểm ~(1,1)~, do đó không cần thêm bất kỳ điểm nào để tạo thành tập hợp có tâm đối xứng.

Test 2: Cần thêm vào ~2~ cột đèn tại các vị trí ~(3,2)~ và ~(3,3)~ để tập hợp có tâm đối xứng là điểm ~(2,2)~.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.