Cơ Hội Chụp Ảnh

Đ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

Bessie bắt đầu tại vị trí $(X, 0)$ và cần đi đến $(0, Y)$ . Có $N$ con bò trên trục $X$ tại tọa độ $(x_{i}, 0)$ , mỗi con có một nhiếp ảnh gia tại $(0, y_{i})$ . Mỗi cặp nhiếp ảnh gia - bò tạo ra một đường ngắm bắt đầu bị chặn từ thời điểm $s_{i}$ .

Bessie sẽ đi đường ngắn nhất (khoảng cách Euclid) đến đích mà không cắt qua bất kỳ đường ngắm nào đang hoạt động. Nếu Bessie xuất phát tại thời điểm $t$ , cô tránh tất cả đường ngắm có $s_{i} \leq t$ .

Hãy tính $⌊ d_{t} ⌋$ cho mỗi $t$ từ $0$ đến $T - 1$ .

Dữ liệu vào

Dòng 1: Hai số $N$ và $T$
Dòng 2: Hai số $X$ và $Y$
$N$ dòng tiếp: Ba số $s_{i}$ , $x_{i}$ , $y_{i}$ cho mỗi con bò

Dữ liệu ra

$T$ dòng, dòng thứ $t$ chứa $⌊ d_{t} ⌋$ .

Ràng buộc

$1 \leq X, Y \leq 10^{6}$
$1 \leq N \leq 3 \cdot 10^{5}$
$1 \leq T \leq N + 1$

Ví dụ

Input	Output	Giải thích
4 5 6 7 1 7 5 2 4 4 3 1 6 4 2 9	9 9 9 10 12	Tại $t = 0$ : không có đường ngắm, đi thẳng $\sqrt{6^{2} + 7^{2}} = \sqrt{85} \approx 9.22$ , $⌊ d_{0} ⌋ = 9$ .

Bình luận

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