Giải bài trực tuyến

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