Olympic chuyên KHTN 2026 - GEOGEBRA
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho ~n~ điểm phân biệt trên mặt phẳng tọa độ ~Oxy~.
Một parabol có phương trình dạng ~y = x^2 + ax + b~ được gọi là thỏa mãn nếu nó đi qua ít nhất ~2~ điểm trong số ~n~ điểm đã cho và không có điểm nào trong số ~n~ điểm nằm phía trên parabol đó.
Yêu cầu: Hãy đếm số lượng parabol thỏa mãn khác nhau.
Input
Dòng đầu tiên chứa số nguyên dương ~n~ ~(2 \le n \le 10^5)~.
~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_{i}, y_{i}~ mô tả tọa độ của điểm thứ ~i~ ~(|x_{i}|, |y_{i}| \le 10^6)~. Các điểm được cho là đôi một phân biệt.
Output
In ra một số nguyên duy nhất là số lượng parabol thỏa mãn tìm được.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~40\%~ | ~n \le 200~ |
| 2 | ~30\%~ | ~n \le 2000~ |
| 3 | ~30\%~ | Không có điều kiện gì thêm |
Sample Input 1
3
0 0
1 1
2 4
Sample Output 1
1
Notes
Một điểm ~(x_{i}, y_{i})~ được gọi là nằm phía trên parabol ~y = x^2 + ax + b~ nếu ~y_{i} > x_{i}^2 + ax_{i} + b~.
Trong ví dụ trên, parabol ~y = x^2~ (với ~a = 0~, ~b = 0~) đi qua cả ~3~ điểm và không có điểm nào nằm phía trên nó.
Bình luận