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.|

MILITARY - Câu chuyện người lính

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/military


“Tôi vẫn nhớ chiến trường Điện Biên năm đó rất ác liệt, rất nhiều người lính đã ngã xuống. Tại vùng căn cứ này, địch cho xây dựng lô cốt, hàng rào dây thép gai rất nhiều , vòng trong nối vòng ngoài, tạo thành nhiều vòng bảo vệ … “Đó là dòng hồi tưởng của 1 người lính già đã từng tham gia chiến dịch Tây Bắc lịch sử. Lần theo những trang sử được ghi chép lại, người ta biết rằng tướng Đờ Cát lúc đầu chưa chọn vị trí để đặt sở chỉ huy mà tìm cách thiết lập các vòng bảo vệ bằng dây thép gai nối các cứ điểm lại với nhau, sau đó sẽ chọn đặt sở chỉ huy tại vị trí an toàn nhất là ở vị trí mà có nhiều vòng bảo vệ bao quanh nhất. Mỗi 1 vòng bảo vệ là 1 đa giác không tự cắt tạo thành bằng cách nối 1 số cứ điểm lại với nhau bằng dây thép gai, 1 cứ điểm thuộc về không quá 1 vòng bảo vệ, các vòng bảo vệ phải được thiết lập sao cho giữa 2 vòng bảo vệ bất kỳ X và Y thì phần diện tích chung của X và Y = Min( diện tích X, diện tích Y ) hoặc = 0. Trên mặt phẳng toạ độ, các cứ điểm được coi như các điểm có toạ độ nguyên. Bạn hãy xác định xem, sở chỉ huy của tướng Đờ Cát sẽ được bảo vệ tối đa bởi mấy vòng bảo vệ.

Download một số test tại đây

Input

Dòng 1: số nguyên N là số cứ điểm. ( 1 ≤ N ≤ 4000 ).
N dòng tiếp theo, dòng thứ i gồm 2 số nguyên xi, yi tương ứng là toạ độ của cứ điểm i . Các toạ độ đều là số nguyên dương ≤ 10000 .

Output

Gồm 1 dòng duy nhất ghi ra số lượng vòng bảo vệ tối đa mà sở chỉ huy của tướng Đờ Cát có thể được bao bọc .

Example

Input:
4
100 100
200 100
100 200
300 300

Output:
1
Giải thích: Ta nối cứ điểm 1, 2, 3, 4 lại tạo thành 1 vòng bảo vệ, đặt trụ sở chỉ huy bên trong thì ra được đáp án. Ngoài ra còn có các phương án khác là nối cứ điểm 1, 2, 3 tạo thành 1 vòng bảo vệ, nối cứ điểm 2, 3, 4 thành 1 vòng bảo vệ, … nhưng tất cả các phương án này thì khi chọn vị trí đặt trụ sở chỉ huy thì vẫn tối đa = 1.

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-02-05
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 PHP PYPY RUST SED VB.NET

hide comments
2022-10-04 16:50:36
thẳng hàng thì vẫn bỏ vào bao lồi nha mng (chú ý hàm ccw)
2019-10-09 11:02:47
18to_nhanh ez
2019-09-08 18:43:45
Bài này test yếu, code mẫu của flashmt sai ở test rất nhỏ nhưng vẫn có thể AC
15
-4 0
-9 0
-6 5
4 8
8 -10
-8 -10
9 3
-1 -8
-9 5
10 5
8 -4
0 6
8 -8
-1 -10
8 0
Đáp án phải là 3.
-Nhật Huy-
2019-07-22 13:39:53
Bạn nào làm bên test mẫu đúng mà qua đây submit sai thì chú ý trường hợp điểm thẳng hàng nhé, tập trung xử lí cái đó thử
2019-01-08 19:23:11
1:22AM 09/01/2019 chỉ còn vài ngày
frostpixel aka.How 2 AC
2017-11-22 10:28:19
Lollipop magic
2016-11-26 16:02:08 Sơn Tùng M-TP
Thẳng hàng thôi.
2016-04-29 13:43:15
Sao ko tải đc các test mẫu??
2015-12-06 16:58:10 Lollipop
e down bộ test về chạy đúng hết sao lại kq sai @@
2015-10-16 06:28:38 [$Zeus$]
chú ý trường hợp thẳng hàng thôi
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.