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

Tầm Nhìn

Đề bài

Mô tả

Nông dân John có N con bò đứng tại các vị trí phân biệt trên đồng cỏ 2D. Tại gốc tọa độ có một silo chứa ngũ cốc hình tròn với bán kính R. Hai con bò có thể nhìn thấy nhau nếu và chỉ nếu đoạn thẳng nối chúng không cắt hoặc tiếp xúc với hình tròn (silo).

Hãy đếm số cặp bò có thể nhìn thấy nhau.

Dữ liệu vào

  • Dòng đầu: hai số nguyên NR.
  • N dòng tiếp theo, mỗi dòng chứa hai số nguyên xy — tọa độ của một con bò.

Dữ liệu ra

  • Một số nguyên duy nhất: số cặp bò có thể nhìn thấy nhau trực tiếp.

Ràng buộc

  • 1N50000
  • 1R1000000
  • 1000000x,y1000000
  • Không có bò nào nằm trên hoặc bên trong silo
  • Không có hai con bò nào nằm trên cùng một đường tiếp tuyến của silo

Ví dụ

Input Output Giải thích
4 5
0 10
0 -10
10 0
-10 0
4 Có 6 cặp tổng cộng. Cặp (0,10)-(0,-10) và cặp (10,0)-(-10,0) bị silo chặn. 4 cặp còn lại nhìn thấy nhau.
50 200
-125 163
-18 -223
228 -101
-125 -180
-202 -22
41 215
121 -231
245 10
-162 -149
147 -139
-206 -75
177 -191
-162 -156
46 -247
-139 161
203 19
-81 200
105 -213
-215 18
177 123
-56 209
244 23
119 -166
183 96
-151 160
243 -45
-229 -104
73 -252
161 -171
-90 211
-223 108
-66 205
-154 142
202 -88
236 60
45 -227
-116 -217
-120 201
242 57
-140 -177
102 204
-85 207
1 -237
-230 -123
92 208
-251 -59
-36 -243
-202 -74
-34 -253
170 -131
378 Trong 1225 cặp tổng cộng, 378 cặp có thể nhìn thấy nhau.

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