레이팅 미적용설명
N개 (1 <= N <= 100,000)의 언덕이 있다. 각 언덕은 (x1, y1)에서 (x2, y2)까지의 선분 형태이며, x1 < x2이고 y1 < y2이다. 이 선분들은 끝점에서조차 서로 교차하거나 맞닿지 않으며, 나아가 첫 번째 언덕은 (x1, y1) = (0,0)을 만족한다.
소 베시(Bessie)는 첫 번째 언덕의 (0,0)에서 출발한다. 베시는 언덕 위에 있을 때마다 끝에 도달할 때까지 올라간다. 그 다음 가장자리에서 뛰어내린다. 다른 언덕에 착지하면 그 언덕을 계속 걸어가고, 그렇지 않으면 아주 멀리 떨어져 y = -무한대에 있는 푹신한 베개 더미에 안전하게 착지한다. 각 언덕 (x1, y1) -> (x2, y2)는 점 (x1, y1)은 포함하지만 점 (x2, y2)는 포함하지 않는 것으로 간주해야 한다. 따라서 베시가 위에서 x = x1인 위치로 떨어지면 그 언덕에 착지하지만, x = x2인 위치로 떨어지면 그 언덕에 착지하지 않는다.
베시가 걷는 동안 어느 시점에든 밟게 되는 언덕의 총수를 세시오.
제약
입력 형식
첫째 줄: 언덕의 수 N.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 언덕 i를 설명하는 네 정수 (x1,y1,x2,y2)가 주어진다. 각 정수는 0..1,000,000,000 범위이다.
출력 형식
베시가 여정 동안 밟는 언덕의 수.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
hillwalk.in · 출력을 쓸 파일 hillwalk.out예제 1
입력
4
0 0 5 6
1 0 2 1
7 2 8 5
3 0 7 7출력
3설명
Output details: Bessie walks on hills #1, #4, and finally #3.
문제 정보
태그