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

Bò qua đường

Đề bài

Mô tả

N con bò đang đi qua một con đường. Con đường nằm giữa y=0y=1. Bò i đi từ điểm (ai,0) đến điểm (bi,1).

Hai bò ij gọi là giao nhau nếu đường đi của chúng cắt nhau (điều này xảy ra khi và chỉ khi (ai<ajbi>bj) hoặc (ai>ajbi<bj)).

Một con bò gọi là an toàn nếu đường đi của nó không giao với đường đi của bất kỳ con bò nào khác.

Hãy đếm số con bò an toàn.

Dữ liệu vào

  • Dòng 1: Số nguyên N
  • Dòng i+1 (với 1iN): Hai số nguyên aibi

Dữ liệu ra

  • Một số nguyên duy nhất: số con bò an toàn

Ràng buộc

  • 1N100000
  • 106ai,bi106
  • Tất cả ai phân biệt, tất cả bi phân biệt

Ví dụ

Input Output Giải thích
4
-3 4
7 8
10 16
3 9
2 Bò 1 (a=3,b=4) và bò 3 (a=10,b=16) an toàn. Bò 2 và bò 4 giao nhau nhau.
10
7 9
-1 1
-8 -9
13 20
16 18
-2 -8
-5 -7
6 4
14 13
-18 -16
5 Có 5 con bò an toàn.

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