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

Xem dạng PDF

Gửi bài giải

Điểm: 1,67 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
USACO December 2008 - Gold Division
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Nông dân John đã mua ~N~ ~(5 \le N \le 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 \le x_i \le 1000~; ~1 \le y_i \le 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 \le 65~.

Input

  • 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~

Output

  • 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

Sample Input

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

Sample Output

5

Note

Các cọc có dạng một hình vuông với 2 điểm bên trong. Đa giác lồi là ngũ giác ~(2,3), (3,2), (5,1), (5,5), (1,5)~.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.