trang chủ / bài tập / lazergun

Súng laser Han Solo

Đề bài

Mô tả

Trên mặt phẳng toạ độ có n mục tiêu, mục tiêu thứ i nằm tại điểm nguyên (xi,yi). Khẩu súng laser đặt tại điểm (x0,y0).

Mỗi phát bắn, súng bắn dọc theo một đường thẳng đi qua (x0,y0) và tiêu diệt tất cả mục tiêu nằm trên đường thẳng đó.

Hãy tính số phát bắn ít nhất để tiêu diệt toàn bộ mục tiêu.

Bảo đảm không có mục tiêu nào nằm trùng với vị trí súng. Nhiều mục tiêu có thể nằm trùng một điểm.

Dữ liệu vào

  • Dòng đầu chứa ba số nguyên n, x0, y0.
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên xi, yi.

Dữ liệu ra

  • In ra một số nguyên duy nhất: số phát bắn ít nhất cần thiết.

Ràng buộc

  • 1n1000
  • 104x0,y0104
  • 104xi,yi104

Ví dụ

Input Output Giải thích
2 1 2
1 1
1 0
1 Hai mục tiêu (1,1)(1,0) cùng nằm trên đường thẳng đứng x=1 đi qua súng, nên chỉ cần một phát bắn.
4 0 0
1 1
2 2
2 0
-1 -1
2 (1,1), (2,2), (1,1) cùng nằm trên đường thẳng y=x; (2,0) nằm trên trục hoành. Hai đường thẳng phân biệt qua gốc, cần hai phát bắ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