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

C11BCH - Bộ chỉ huy

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


Sirdat_LS có căn cứ quân sự được thiết lập sâu trong rừng rậm. Có n trạm gác đặt máy phát siêu âm để bảo vệ căn cứ, trạm thứ i có tọa độ (xi, yi). Không có 3 trạm nào thẳng hàng. Nếu lấy các trạm này làm đỉnh ta có một đa giác lồi. Không có trạm nào nằm trong đa giác lồi. Vùng nằm hoàn toàn trong đa giác lồi được bảo vệ an toàn tuyệt đối. Nhưng Khaihankdk có thể tấn công và phá hủy một số trạm gác. Với những trạm còn lại, vùng được bảo vệ sẽ bị thu hẹp.

Bộ chỉ huy của Sirdat_LS cần phải được đảm bảo an toàn ở mức cao nhất, sao cho để Bộ chỉ huy không còn được an toàn địch phải phá hủy một số nhiều nhất các trạm gác.

 

Cần phá 2 trạm gác

Yêu cầu: Cho n và các  tọa độ nguyên xi, yi (3 ≤ n ≤ 5×104, |xi|, |yi| ≤ 106, i = 1 ÷ n). Hãy xác định số trạm gác tối đa cần phá để Bộ chỉ huy không còn được an toàn ứng với trường hợp vị trí đặt bộ chỉ huy được chọn tối ưu.

Input

  • Dòng đầu tiên chứa số nguyên n,
  • Dòng thứ i trong n dòng sau chứa 2 số nguyên xi, yi, các đỉnh được liệt kê theo chiều kim đồng hồ.

Output

Một số nguyên duy nhất – số trạm gác tối đa cần phá để Bộ chỉ huy không còn được an toàn.

Example

Input:
5
0 0
0 10
10 20
20 10
25 0 Output: 2

Được gửi lên bởi:Hacker7
Ngày:2011-11-25
Thời gian chạy:2s
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ừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:NEERC 2010

hide comments
2016-09-27 03:31:06
Code:
http://shink.in/8pF6C
2011-11-26 21:26:15 Nguyên
NEERC 2010
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.