Điều hướng chính

Ngôn ngữ

Phím tắt

/
Chuyển đến ô tìm bài
g p
Đi đến bài tập
g c
Đi đến kỳ thi
g u
Đi đến người dùng
?
Mở trợ giúp phím tắt

Hill Walk

Dễ

  • 100 Điểm
  • 0% Tỉ lệ AC
  • 0 Số AC
  • 256M Bộ nhớ giới hạn
  • 1.0s Giới hạn thời gian

Có \(N\) ngọn đồi \((1 \le N \le 100000)\), mỗi ngọn đồi là một đoạn thẳng từ \((x_1,y_1)\) đến \((x_2,y_2)\) thỏa
\(x_1 < x_2\) và \(y_1 < y_2\).
Không có hai đoạn thẳng nào cắt nhau hoặc chạm nhau, kể cả tại đầu mút.
Ngoài ra, ngọn đồi thứ nhất có \((x_1,y_1)=(0,0)\).

Bessie bắt đầu tại điểm \((0,0)\) trên ngọn đồi thứ nhất.
Khi đang ở trên một ngọn đồi, Bessie đi lên theo đoạn thẳng cho đến khi tới đầu mút phải (điểm có hoành độ \(x_2\)), rồi nhảy khỏi mép.
Sau đó Bessie rơi thẳng đứng xuống dưới (giữ nguyên hoành độ).
Nếu trong quá trình rơi Bessie chạm vào một ngọn đồi khác thì Bessie tiếp tục đi trên ngọn đồi đó theo quy tắc như trên;
nếu không chạm ngọn đồi nào thì Bessie rơi mãi xuống rất sâu (coi như tới \(y=-\infty\)) và hành trình kết thúc.

Quy ước: mỗi ngọn đồi \((x_1,y_1)\rightarrow(x_2,y_2)\) có chứa điểm \((x_1,y_1)\) nhưng không chứa điểm \((x_2,y_2)\).
Vì vậy, nếu Bessie rơi tại hoành độ \(x=x_1\) thì sẽ được coi là rơi xuống ngọn đồi đó, còn nếu rơi tại \(x=x_2\) thì không.

Hãy đếm tổng số ngọn đồi mà Bessie chạm vào trong suốt hành trình.

\InputFile

  • Dòng 1: số nguyên \(N\).(\(1 \le N \le 10^5\))
  • \(N\) dòng tiếp theo: mỗi dòng gồm bốn số nguyên \(x_1,y_1,x_2,y_2\) mô tả một ngọn đồi.
    Mỗi số nguyên nằm trong đoạn \([0,10^9]\).

\OutputFile
In ra một số nguyên duy nhất: số ngọn đồi mà Bessie chạm vào.

Example

Test 1

Input
4
0 0 5 6
1 0 2 1
7 2 8 5
3 0 7 7
Output
3

Test 2

Input
2
0 0 5 100
1 1 5 5
Output
1

Bình luận

Chưa có bình luận nào.