Điểm tốt trong không gian 5 chiều

Đề bài

Mô tả

Cho n điểm trong không gian 5 chiều, được đánh số từ 1 đến n. Không có hai điểm nào trùng nhau.

Ta gọi điểm axấu nếu tồn tại hai điểm khác nhau bc (cả hai đều khác a) sao cho góc giữa hai vector abacgóc nhọn (tức là nhỏ hơn 90 một cách chặt). Ngược lại, điểm a được gọi là tốt.

Góc giữa hai vector là góc thông thường trong không gian Euclid; góc này nhọn khi và chỉ khi tích vô hướng của hai vector dương.

Hãy in ra chỉ số của tất cả các điểm tốt theo thứ tự tăng dần.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n.
  • n dòng tiếp theo, dòng thứ i chứa năm số nguyên ai,bi,ci,di,ei là toạ độ của điểm thứ i.

Dữ liệu ra

  • Dòng đầu in ra số nguyên k: số lượng điểm tốt.
  • k dòng tiếp theo, mỗi dòng in ra chỉ số của một điểm tốt theo thứ tự tăng dần.

Ràng buộc

  • 1n103
  • |ai|,|bi|,|ci|,|di|,|ei|103
  • Tất cả các điểm đôi một phân biệt.

Ví dụ

Input Output Giải thích
6
0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1
1
Điểm 1 nằm ở gốc; các vector từ nó tới mọi điểm khác đôi một vuông góc nên không có góc nhọn nào, do đó điểm 1 tốt. Các điểm còn lại đều xấu.
3
0 0 1 2 0
0 0 9 2 0
0 0 5 9 0
0 Với mỗi điểm đều tồn tại một cặp vector tạo với nhau góc nhọn, nên không có điểm nào tốt.

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