Hình chữ nhật kỳ lạ

Đề bài

Mô tả

Trên mặt phẳng có N điểm phân biệt, điểm thứ i nằm tại tọa độ (xi,yi).

Xét một vùng chữ nhật đặc biệt được xác định bởi ba đường thẳng: x=l (cạnh trái), y=a (cạnh dưới) và x=r (cạnh phải), với l<r. Cạnh trên của vùng kéo dài vô hạn lên phía trên. Một điểm (xi,yi) nằm trong vùng khi và chỉ khi l<xi<ryi>a, trong đó l, r, a có thể là số thực bất kỳ.

Với mỗi vùng như vậy, ta thu được tập các điểm nằm bên trong nó. Hãy đếm số tập khác nhau, không rỗng có thể thu được. Hai tập được coi là khác nhau nếu tồn tại ít nhất một điểm thuộc tập này nhưng không thuộc tập kia.

Dữ liệu vào

  • Dòng đầu chứa số nguyên N, số điểm trên mặt phẳng.
  • N dòng tiếp theo, dòng thứ i chứa hai số nguyên xiyi, tọa độ của điểm thứ i.

Tất cả các điểm đều phân biệt.

Dữ liệu ra

In ra một số nguyên duy nhất: số tập điểm khác nhau, không rỗng có thể thu được.

Ràng buộc

  • 1N2×105
  • 1xi,yi109
  • Các điểm đôi một phân biệt.

Ví dụ

Input Output Giải thích
3
1 1
1 2
1 3
3 Ba điểm cùng nằm trên một cột. Với mỗi k=1,2,3 có đúng một tập gồm k điểm (chọn k điểm cao nhất), tổng cộng 3 tập.
3
1 1
2 1
3 1
6 Ba điểm cùng nằm trên một hàng. Số tập gồm 1,2,3 điểm lần lượt là 3,2,1, tổng cộng 6.
4
2 1
2 2
3 1
3 2
6 2 tập một điểm, 3 tập hai điểm và 1 tập bốn điểm: 2+3+1=6.

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