Chứng Cứ Ngoại Phạm

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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

Một con bò đã ăn trộm cỏ tại nhiều khu vườn vào những thời điểm khác nhau. Mỗi trong $N$ con bò của nông dân John có một chứng cứ ngoại phạm đặt chúng tại một vị trí cụ thể vào một thời điểm cụ thể.

Một con bò được coi là vô tội nếu không thể di chuyển giữa tất cả các vụ ăn trộm và vị trí ngoại phạm của nó, biết rằng bò di chuyển với tốc độ tối đa 1 đơn vị khoảng cách trên 1 đơn vị thời gian (khoảng cách Euclidean).

Hãy đếm số bò có chứng cứ ngoại phạm chứng minh được sự vô tội.

Dữ liệu vào

Dòng 1: Hai số nguyên $G$ và $N$ ( $1 \leq G, N \leq 10^{5}$ ) — số vụ ăn trộm và số con bò.
$G$ dòng tiếp theo: Ba số nguyên $x$ , $y$ , $t$ ( $- 10^{9} \leq x, y \leq 10^{9}$ , $0 \leq t \leq 10^{9}$ ) — vị trí và thời gian mỗi vụ ăn trộm.
$N$ dòng tiếp theo: Ba số nguyên $x$ , $y$ , $t$ — vị trí và thời gian ngoại phạm mỗi con bò.

Luôn tồn tại cách một con bò duy nhất di chuyển qua tất cả các vụ ăn trộm.

Dữ liệu ra

Một số nguyên duy nhất — số con bò được chứng minh vô tội.

Ràng buộc

$1 \leq G, N \leq 10^{5}$
$- 10^{9} \leq x, y \leq 10^{9}$
$0 \leq t \leq 10^{9}$
Giới hạn thời gian: 4 giây

Ví dụ

Input	Output	Giải thích
2 4 0 0 100 50 0 200 0 50 50 1000 1000 0 50 0 200 10 0 170	2	Bò 1 ở (0,50) lúc t=50 không thể đến (0,0) lúc t=100 rồi (50,0) lúc t=200 (khoảng cách 50 trong 50 giây, vừa đủ). Bò 2 ở (1000,1000) lúc t=0 quá xa. Bò 3 trùng vị trí vụ ăn trộm. Bò 4 ở (10,0) lúc t=170 cần đến (50,0) lúc t=200, khoảng cách 40 trong 30 giây — bất khả thi nhưng thực ra chỉ cần kiểm tra 2 vụ gần nhất về thời gian.

Bình luận

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