Hình chữ nhật và hình vuông

Đề bài

Mô tả

Cho 8 điểm phân biệt trên mặt phẳng. Hãy chia 8 điểm này thành hai nhóm, mỗi nhóm gồm đúng 4 điểm, sao cho:

  • 4 điểm của nhóm thứ nhất là các đỉnh của một hình vuông, và
  • 4 điểm của nhóm thứ hai là các đỉnh của một hình chữ nhật.

Mỗi điểm trong 8 điểm ban đầu phải thuộc đúng một nhóm. Hình chữ nhật ở nhóm thứ hai cũng có thể đồng thời là một hình vuông. Cả hình vuông lẫn hình chữ nhật đều phải có diện tích khác 0.

Các cạnh của hai hình không nhất thiết phải song song với các trục tọa độ.

Dữ liệu vào

Gồm 8 dòng, dòng thứ i chứa hai số nguyên xiyi — tọa độ của điểm thứ i.

Dữ liệu ra

Nếu tồn tại cách chia hợp lệ, in ra:

  • Dòng đầu tiên: từ YES.
  • Dòng thứ hai: 4 chỉ số (các điểm được đánh số từ 1) của các điểm tạo thành hình vuông, cách nhau bởi dấu cách.
  • Dòng thứ ba: 4 chỉ số của các điểm tạo thành hình chữ nhật.

Các chỉ số có thể in theo thứ tự bất kỳ; cả 8 chỉ số in ra phải đôi một khác nhau.

Nếu không tồn tại cách chia hợp lệ, chỉ in ra một dòng chứa từ NO.

Nếu có nhiều cách chia hợp lệ, in ra cách bất kỳ.

Ràng buộc

  • Tọa độ là số nguyên, |xi|,|yi|104.
  • Không có hai điểm nào trùng nhau.

Ví dụ

Input Output Giải thích
0 0
10 11
10 0
0 11
1 1
2 2
2 1
1 2
YES
5 6 7 8
1 2 3 4
Các điểm 5,6,7,8 tạo thành hình vuông cạnh 1; các điểm 1,2,3,4 tạo thành hình chữ nhật 10×11.
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
NO Tất cả 8 điểm thẳng hàng, không thể tạo thành hình vuông hay hình chữ nhật nào.
0 0
4 4
4 0
0 4
1 2
2 3
3 2
2 1
YES
1 2 3 4
5 6 7 8
Các điểm 1,2,3,4 tạo thành hình vuông cạnh 4; các điểm 5,6,7,8 tạo thành hình vuông (cũng là hình chữ nhật) có cạnh nghiêng so với trụ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 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