Page not loading? Try clicking here.
Placeholder

#3827

오리가 얼면? 1s 128MB

Problems

오리가 얼면? 언덕(Duck)이다.

오리는 얼어 죽지 않기 위해 열심히 언덕을 오르며 운동을 하고 있다.

N개의 언덕이 있다. 각 언덕은 (x1, y1)부터 (x2, y2)까지의 선분 형태를 가지며, 여기서 x1 \lt x2이고 y1 < y2이다. 이들 선분은 교차하지 않으며, 끝점에서도 만나지 않으며, 첫 번째 언덕은 (0, 0)에서 시작한다.

오리는 첫 번째 언덕의 (0, 0)에서 출발한다. 오리는 언덕 위에 있는 동안 맨 꼭대기까지 올라가고 언덕 끝에서 뛰어내린다. 여기서 뛰어내린다의 정의는 x좌표는 변하지 않고, y좌표가 감소함을 의미한다. 다른 언덕에 착지하면 그 언덕을 따라 걷지만 그렇지 않으면 아주 멀리 떨어진 곳으로 떨어져서 y=-\infty인 오리털 베개 위에 안전하게 착지한다. 각 언덕 (x1, y1) -> (x2, y2)는 (x1, y1)을 포함하지만 (x2, y2)는 포함하지 않는 것으로 간주된다. 따라서 오리는 x = x1인 위치에 떨어지면 해당 언덕에 착지하지만, x = x2인 위치에 떨어지면 해당 언덕에 착지하지 않는다.

오리가 산책 도중 접촉하는 총 언덕 수를 계산하자.


Input

첫 번째 줄에 언덕의 수 N이 입력된다 (1 \le N \le 100,000).

두 번째 줄부터 N+1번째 줄까지 i+1번째 줄에는 언덕 i의 좌표인 네 개의 정수 (x1, y1, x2, y2)가 주어진다. 각 정수는 0에서 1,000,000,000 사이이다.


Output

첫 번째 줄에 오리가 산책 도중 접촉하는 언덕의 수를 출력하시오.


Subtask

# Score Condition
#130

N \le 2000

#270

추가 제한 없음


Example 

5
0 0 5 9
1 0 2 1
8 4 10 10
7 2 8 5
3 0 7 7
4

Source

USACO 2013 March Gold

You must sign in to write code.