trang chủ / đề bài / icpc20_nat_k

Vương quốc Mèo

Đề bài

Mô tả

Có thể bạn vẫn còn nhớ bài Kingdom of Kittens trong kỳ thi ICPC Asia Hanoi Regional 2018. Hai năm đã trôi qua, vương quốc ấy đã phát triển thành Vương quốc Mèo, với những bài toán còn khó hơn.

Khi vương quốc lớn dần, những chú mèo cần vạch một đường biên giới mới. Chúng đã tìm được n bụi cây đẹp và quyết định dùng các bụi cây này để đánh dấu biên giới.

Không may, mèo không giỏi hình học lắm, nên chúng muốn biên giới là một đa giác có đúng bốn cạnh. Ngoài ra, để tránh nhầm lẫn, với mọi cặp điểm nằm trong đa giác, mọi điểm trên đoạn thẳng nối hai điểm đó cũng phải nằm trong đa giác. Nói cách khác, biên giới phải là một đa giác lồi. Vì kế hoạch vẫn đang được bàn bạc, những chú mèo muốn bạn cho biết có bao nhiêu cách chọn biên giới thỏa mãn mọi yêu cầu của chúng.

Nói một cách chính xác: cho n điểm trên mặt phẳng tọa độ, hãy đếm số tứ giác lồi có diện tích dương mà cả 4 đỉnh đều thuộc n điểm đã cho.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu có dạng:

  • Dòng đầu tiên chứa một số nguyên dương n, số điểm (1≤n≤50).
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên xi và yi, tọa độ của điểm thứ i (−109≤xi,yi≤109). Không có hai điểm nào trùng tọa độ.

Dữ liệu vào kết thúc bằng một dòng chứa số 0.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa số tứ giác lồi khác nhau thỏa mãn các điều kiện trên.

Ràng buộc

  • 1≤n≤50
  • Tổng n của tất cả các bộ dữ liệu không vượt quá 500.
  • −109≤xi,yi≤109, các điểm đôi một phân biệt.

Ví dụ

Input Output Giải thích
7
4 1
3 1
2 1
1 1
1 2
1 3
1 4
4
0 0
0 2
2 0
2 2
0
9
1
Bộ thứ nhất: các điểm nằm trên hai tia vuông góc chung gốc (1,1). Một tứ giác lồi phải lấy đúng 2 trong 3 điểm (2,1),(3,1),(4,1) và đúng 2 trong 3 điểm (1,2),(1,3),(1,4) (ba đỉnh thẳng hàng thì không tạo thành tứ giác lồi), nên có 3·3=9 cách. Bộ thứ hai: 4 điểm là 4 đỉnh của một hình vuông.
5
0 0
4 0
0 4
1 1
3 3
4
0 0
1 1
2 2
3 3
0
2
0
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: hai tứ giác lồi là (0,0),(4,0),(3,3),(0,4) và (4,0),(3,3),(0,4),(1,1). Mọi cách chọn khác hoặc có ba điểm thẳng hàng trên đường y=x, hoặc có (1,1) nằm trong tam giác (0,0),(4,0),(0,4). Bộ thứ hai: bốn điểm thẳng hàng.

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