trang chủ / bài tập / hillwalk

Đi Trên Đồi

Đề bài

Mô tả

N đoạn dốc (hill), mỗi đoạn là một đoạn thẳng từ điểm (x1,y1) đến (x2,y2) với x1<x2y1<y2 (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 (x2,y2), 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=x2 với độ cao y thỏa mãn yy2 (và đoạn dốc đó chứa điểm x2 theo nghĩa x1x2<x2 — đ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 (1N100000)
  • N dòng tiếp theo: Bốn số nguyên x1,y1,x2,y2 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

  • 1N100000
  • 0x1,y1,x2,y2109

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.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0