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

Cặp đoạn lồng nhau

Đề bài

Mô tả

Cho n đoạn thẳng trên một trục số, được đánh số từ 1 đến n. Đoạn thẳng thứ i được cho bởi hai đầu mút liri.

Nhiệm vụ của bạn là tìm hai chỉ số phân biệt ij sao cho đoạn thẳng thứ i nằm trọn bên trong đoạn thẳng thứ j.

Đoạn thẳng [l1,r1] được gọi là nằm trọn bên trong đoạn thẳng [l2,r2] khi và chỉ khi l1l2r1r2 (cho phép hai đầu mút trùng nhau).

Nếu có nhiều cặp thỏa mãn, in ra một cặp bất kỳ. Nếu không tồn tại cặp nào, in ra 1 1.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n — số lượng đoạn thẳng.
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên liri.

Dữ liệu ra

In ra hai chỉ số phân biệt ij sao cho đoạn thẳng thứ i nằm trọn bên trong đoạn thẳng thứ j. Nếu có nhiều đáp án, in ra một đáp án bất kỳ. Nếu không tồn tại, in ra 1 1.

Ràng buộc

  • 1n3·105
  • 1liri109

Ví dụ

Input Output Giải thích
5
1 10
2 9
3 9
2 3
2 9
2 1 Đoạn [2,9] nằm trọn trong đoạn [1,10]. Nhiều cặp khác cũng hợp lệ, chẳng hạn 3 1 hay 4 2, in ra cặp nào cũng được.
3
1 5
2 6
6 20
-1 -1 Không có đoạn nào nằm trọn bên trong một đoạn khác.

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 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