trang chủ / đề bài / icpc26_mt_l

Phân loại tứ giác

Đề bài

Mô tả

Tuấn vừa học về các loại tứ giác và muốn thử khả năng nhận biết của mình.

Cho N điểm trên mặt phẳng tọa độ Oxy, được đánh số từ 1 đến N. Hai hay nhiều điểm ban đầu có thể trùng tọa độ.

Tuấn chọn một bộ 4 điểm có chỉ số khác nhau (i,j,k,l) với 1≤i<j<k<l≤N. Một bộ 4 điểm được coi là một tứ giác hợp lệ nếu thỏa mãn đồng thời hai điều kiện:

  • Bốn điểm được chọn có tọa độ đôi một khác nhau.
  • Không có ba điểm nào trong bốn điểm được chọn thẳng hàng.

Mỗi bộ 4 chỉ số khác nhau được tính là một cách chọn riêng, kể cả khi một số điểm trùng tọa độ.

Với mỗi bộ 4 điểm hợp lệ, hãy xác định chúng tạo thành những loại tứ giác nào:

  • Hình vuông (S): có 4 cạnh bằng nhau và 1 góc vuông.
  • Hình chữ nhật (R): có 4 góc vuông.
  • Hình thoi (H): có 4 cạnh bằng nhau.
  • Hình thang (T): có ít nhất 1 cặp cạnh đối song song.
  • Hình bình hành (P): có 2 cặp cạnh đối song song.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên N (4≤N≤1000).
  • N dòng tiếp theo, dòng thứ i chứa hai số nguyên xi,yi (−109≤xi,yi≤109) là tọa độ điểm thứ i.

Dữ liệu ra

In ra 5 số nguyên trên một dòng, cách nhau bởi dấu cách, lần lượt là số bộ 4 điểm tạo thành hình vuông (S), hình chữ nhật (R), hình thoi (H), hình thang (T) và hình bình hành (P).

Ràng buộc

  • 4≤N≤1000.
  • −109≤xi,yi≤109.

Ví dụ

Input Output Giải thích
5
0 0
0 1
0 1
1 0
1 1
2 2 2 2 2 Điểm 2 và điểm 3 trùng tọa độ (0,1). Có hai bộ hợp lệ là (1,2,4,5) và (1,3,4,5), cả hai đều là hình vuông cạnh 1; một hình vuông đồng thời là hình chữ nhật, hình thoi, hình thang và hình bình hành. Các bộ còn lại chứa cả điểm 2 và điểm 3 nên không hợp lệ.
4
0 0
4 0
3 2
1 2
0 0 0 1 0 Bốn điểm tạo thành hình thang có hai đáy nằm trên các đường y=0 và y=2; hai cạnh bên không song song nên không phải hình bình hành.

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