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

Có $N$ con bò đang di chuyển sang phải trên mặt phẳng. Con bò thứ $i$ có tọa độ ban đầu $(x_{i}, y_{i})$ tại thời điểm $t = 0$ (với $x_{i} < 0$ ), chiều dài 1 đơn vị (từ $x_{i}$ đến $x_{i} + 1$ ) và tốc độ $1 / r_{i}$ đơn vị mỗi đơn vị thời gian.

Một người đứng tại gốc tọa độ $(0, 0)$ nhìn theo chiều dương trục $y$ . Con bò $i$ được nhìn thấy khi nó cắt trục $y$ (tức là $x = 0$ ). Một con bò bị khuất hoàn toàn nếu trong suốt thời gian nó cắt trục $y$ , luôn có một con bò khác có $y$ nhỏ hơn (gần người quan sát hơn) cũng đang cắt trục $y$ tại mỗi thời điểm đó.

Đếm số con bò mà người quan sát có thể thấy.

Dữ liệu vào

Dòng đầu chứa số nguyên $N$ .

$N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x_{i}$ , $y_{i}$ , $r_{i}$ .

Dữ liệu ra

Số con bò có thể nhìn thấy.

Ràng buộc

$1 \leq N \leq 50000$
$- 1000 \leq x_{i} \leq - 1$
$1 \leq y_{i} \leq 1000000$ (phân biệt)
$1 \leq r_{i} \leq 1000000$

Ví dụ

Input	Output	Giải thích
3 -2 1 3 -3 2 3 -5 100 1	2	Con bò 1 cắt trục $y$ trong $[3, 6]$ , con bò 2 trong $[6, 9]$ , con bò 3 trong $[4, 5]$ . Con bò 3 ( $y = 100$ ) bị khuất bởi con bò 1 ( $y = 1$ ) suốt $[4, 5]$ .

Bình luận

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