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
Đăng nhập để bình luận
Chưa có bình luận nào.