FENCE - Hàng rào lớn nhất

Giới hạn

• Thời gian: 0.2s
• 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

Nông dân John đã mua N (5 <= N <= 250) cái cọc để xây một hàng rào thật đẹp. Một cái hàng rào là đẹp nếu nó có dạng 1 đa giác lồi với các đỉnh là các cọc. Coi đồng cỏ như mặt phẳng tọa độ thì cọc i được cắm ở điểm tọa độ là (x_i, y_i) (1 <= x_i <= 1,000; 1 <= y_i <= 1000; x_i, y_i là số nguyên).

Biết rằng không có 3 cọc nào thẳng hàng với nhau. Hãy tính xem có thể chọn được nhiều nhất bao nhiêu cái cọc để lập được 1 cái hàng rào đẹp.

45% điểm cho bài này là các test có N <= 65.

QUY CÁCH NHẬP DỮ LIỆU

• Dòng 1: Một số nguyên: N
• Dòng 2..N+1: Dòng i+1 mô tả tọa độ của cọc thứ i là 2 số nguyên cách nhau bởi dấu cách: x_i và y_i

VÍ DỤ

6
5 5
2 3
3 2
1 5
5 1
1 1

MÔ TẢ VÍ DỤ

Các cọc có dạng một hình vuông với 2 điểm bên trong.

QUY CÁCH GHI KẾT QUẢ

• Dòng 1: Một số nguyên, số cọc tối đa có thể tạo thành một đa giác lồi

VÍ DỤ

5

GIẢI THÍCH

Đa giác lồi là ngũ giác (2,3), (3,2), (5,1), (5,5), (1,5).

---

• Người up: paulmcvn
• Nguồn bài: USACO December 2008 - Gold Division