Đi Trên Đồi

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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$ đoạn dốc (hill), mỗi đoạn là một đoạn thẳng từ điểm $(x_{1}, y_{1})$ đến $(x_{2}, y_{2})$ với $x_{1} < x_{2}$ và $y_{1} < y_{2}$ (dốc đi lên từ trái sang phải). Các đoạn dốc không giao nhau.

Bạn bắt đầu tại $(0, 0)$ trên đoạn dốc đầu tiên và đi theo hướng tăng $x$ . Khi đến đầu phải của một đoạn dốc $(x_{2}, y_{2})$ , bạn nhảy thẳng xuống theo phương thẳng đứng. Nếu có đoạn dốc khác tại $x = x_{2}$ với độ cao $y$ thỏa mãn $y \leq y_{2}$ (và đoạn dốc đó chứa điểm $x_{2}$ theo nghĩa $x_{1} \leq x_{2} < x_{2}^{'}$ — điểm trái đóng, điểm phải mở), bạn tiếp tục đi trên đoạn dốc đó. Nếu không, bạn rơi mãi mãi.

Đếm tổng số đoạn dốc bạn đã chạm vào trong hành trình.

Dữ liệu vào

Dòng 1: Số nguyên $N$ ( $1 \leq N \leq 100000$ )
$N$ dòng tiếp theo: Bốn số nguyên $x_{1}, y_{1}, x_{2}, y_{2}$ mô tả mỗi đoạn dốc

Dữ liệu ra

Số nguyên: tổng số đoạn dốc đã chạm.

Ràng buộc

$1 \leq N \leq 100000$
$0 \leq x_{1}, y_{1}, x_{2}, y_{2} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 0 0 5 6 1 0 2 1 7 2 8 5 3 0 7 7	3	Đi qua đoạn 1 (0,0)→(5,6), nhảy xuống đoạn 4 (3,0)→(7,7), nhảy xuống đoạn 3 (7,2)→(8,5), rồi rơi.

Bình luận

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