NKPOLI - Đa giác

Giới hạn

• Thời gian: 0.119s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Có N điểm trên mặt phẳng với tọa độ là các số tự nhiên. Một đa giác lồi nhiều đỉnh nhất là một đa giác lồi có các đỉnh là gốc tọa độ và một số đỉnh trong các điểm đã cho, và có số đỉnh là nhiều nhất. Điểm gốc, nghĩa là điểm có tọa độ (0, 0), phải là một trong các đỉnh của đa giác lồi nhiều đỉnh nhất .

Viết chương trình xác định số đỉnh của đa giác này.

Một đa giác là lồi nếu mọi đoạn thẳng có đầu mút nằm trong đa giác đều nằm hoàn toàn trong đa giác đó.

Các cạnh liên tiếp của một đa giác không được phép song song với nhau.

Dữ liệu

• Dòng đầu tiên chứa số tự nhiên N, 2 ≤ N ≤ 100, số điểm được cho.
• Mỗi dòng trong số N dòng tiếp theo chứa 2 số tự nhiên X, Y, 1 ≤ X ≤ 100, 1 ≤ Y ≤ 100 cách nhau bởi khoảng trắng, cho biết tọa độ của một điểm. Các điểm đều phân biệt nhau.

Kết qủa

In ra một số nguyên duy nhất là số đỉnh của đa giác lồi nhiều đỉnh nhất .

Lưu ý: kết quả luôn không nhỏ hơn 3.

Ví dụ

Dữ liệu:
5
4 2
2 2
2 3
3 2
3 1

Kết qủa
4

Dữ liệu:
8
10 8
3 9
2 8
2 3
9 2
9 10
10 3
8 10

Kết qủa
8

Dữ liệu:
10
9 6
1 7
2 2
3 9
8 7
3 2
9 4
3 1
9 7
6 9

Kết quả:
7

---

• Người up: paulmcvn
• Nguồn bài: Croatian OI 2001