Tầm Nhìn

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 $N$ và $R$ .
$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $y$ — 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

$1 \leq N \leq 50 000$
$1 \leq R \leq 1 000 000$
$- 1 000 000 \leq x, y \leq 1 000 000$
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.