Parabol chữ U

Đề bài

Mô tả

Cho hai điểm có hoành độ khác nhau, tồn tại duy nhất một parabol đi qua hai điểm đó có phương trình dạng y=x2+bx+c, với b,c là các số thực. Gọi parabol như vậy là parabol chữ U.

Trên mặt phẳng có n điểm phân biệt với toạ độ nguyên. Với mỗi cặp điểm có hoành độ khác nhau, ta vẽ một parabol chữ U đi qua hai điểm đó. Hãy đếm số parabol đã vẽ mà không có điểm nào trong n điểm cho trước nằm bên trong miền giới hạn bởi parabol đó.

Miền bên trong của một parabol chữ U là phần mặt phẳng nằm nghiêm ngặt phía trên đường parabol (trục y hướng lên).

Dữ liệu vào

  • Dòng đầu chứa số nguyên n — số điểm.
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên xi,yi — toạ độ điểm thứ i.

Dữ liệu ra

In ra một số nguyên — số parabol chữ U đi qua ít nhất hai điểm và không có điểm nào trong n điểm cho trước nằm bên trong miền của parabol (không kể chính các điểm nằm trên parabol).

Ràng buộc

  • 1n105.
  • |xi|,|yi|106.
  • Tất cả các điểm đều phân biệt.

Ví dụ

Input Output Giải thích
3
-1 0
0 2
1 0
2 Có 3 cặp điểm hoành độ khác nhau, vẽ được 3 parabol. Hai parabol đi qua điểm (0,2) không chứa điểm nào bên trong; parabol còn lại đi qua (1,0)(1,0) chứa điểm (0,2) bên trong miền.
5
1 0
1 -1
0 -1
-1 0
-1 -1
1 Chỉ một parabol đi qua hai trong số các điểm mà không có điểm nào nằm nghiêm ngặt phía trên nó.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0