Square Pasture

Đề bài

Mô tả

Farmer John có N con bò trên mặt phẳng tọa độ, con bò thứ i đứng tại điểm (xi,yi).

FJ muốn dựng một hàng rào hình vuông có các cạnh song song với hai trục tọa độ. Một con bò được xem là bị bao quanh nếu nó nằm bên trong hoặc nằm trên cạnh của hình vuông.

Vị trí và độ dài cạnh của hình vuông là các số thực tùy ý (không bắt buộc là số nguyên), độ dài cạnh có thể bằng 0.

Hãy đếm số tập con bò phân biệt mà FJ có thể bao quanh bằng một hàng rào như vậy. Tập rỗng cũng được tính, vì FJ luôn có thể dựng hàng rào ở nơi không có con bò nào.

Dữ liệu vào

  • Dòng 1: số nguyên N
  • N dòng tiếp theo: hai số nguyên xi, yi, tọa độ của con bò thứ i

Dữ liệu ra

Một số nguyên: số tập con bò phân biệt có thể bao quanh.

Ràng buộc

  • 1≤N≤200
  • 0≤xi,yi≤109
  • Tất cả tọa độ x phân biệt, tất cả tọa độ y phân biệt
  • Kết quả nằm trong phạm vi số nguyên có dấu 32 bit

Ví dụ

Input Output Giải thích
4
0 2
2 3
3 1
1 0
14 Trong 16 tập con, chỉ có hai tập không bao được là {(0,2),(3,1)} và {(2,3),(1,0)}: hình vuông nhỏ nhất chứa hai con bò của mỗi tập đó luôn chứa thêm ít nhất một con bò khác. Vậy đáp án là 16−2=14.
6
1 5
4 1
0 4
5 2
3 0
2 3
34 Ví dụ tập {(0,4),(2,3),(4,1)} bao được bằng hình vuông [0,4]×[0.5,4.5]: hình vuông này loại được (3,0) ở dưới và (1,5) ở trên. Không có hình vuông cạnh 4 với tọa độ nguyên nào bao đúng ba con bò này.

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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0