Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKPOLI - Đa giác

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkpoli


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

Được gửi lên bởi:Jimmy
Ngày:2008-01-02
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Croatian OI 2001

hide comments
2016-10-26 10:55:12 minhsn
Im
2011-10-27 16:48:25 Noyethug
có vẻ như ý bài này là k có 3 điểm liên tiếp nào thằng hàng......:)
2011-04-08 18:56:27 vu tien luc
@lee ko phai la "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. " du . tai vi` 2 canh lien tiep neu // thi` se~ cung nam tren 1 doan thang? . see ya !!
2010-12-04 08:31:01 ðẹp trai ri bay
bài này đề khó hiểu vậy
2010-03-14 02:17:32 lee
khó nhỉ. dữ kiện "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ư" phải không

Last edit: 2010-03-14 02:22:02
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.