trang chủ / đề bài / icpc21_nat_c

Tam giác bằng nhau

Đề bài

Mô tả

Trong hình học, hai tam giác được gọi là bằng nhau khi và chỉ khi chúng có cùng kích thước và hình dạng. Nói cách khác, mọi cặp góc trong tương ứng có số đo bằng nhau, và mọi cặp cạnh tương ứng có cùng độ dài. Chính xác hơn, tam giác ABC bằng tam giác DEF, ký hiệu △ABC≅△DEF, khi và chỉ khi cả sáu mệnh đề sau đều đúng:

  • AB=DE
  • BC=EF
  • CA=FD
  • ∠ABC=∠DEF
  • ∠BCA=∠EFD
  • ∠CAB=∠FDE

Lưu ý rằng khi phát biểu hai tam giác bằng nhau, thứ tự các đỉnh là quan trọng. Ví dụ, khi nói △ABC≅△DEF, ta hiểu cạnh AB tương ứng với cạnh DE, góc ∠BCA tương ứng với góc ∠EFD, v.v. Chẳng hạn, nếu △ABC≅△DEF thì △ACB≅△DFE cũng đúng (vẫn là cùng một cách cho các đỉnh tương ứng), còn △ABC≅△FED sẽ sai nếu AB≠FE.

Trong bài này, bạn được cho n điểm trên mặt phẳng tọa độ, ký hiệu P1,P2,…,Pn. Tọa độ của điểm Pk là (xk,yk). Hãy đếm số cặp tam giác bằng nhau có 6 đỉnh là 6 điểm phân biệt trong các điểm đã cho.

Chính xác hơn, hãy đếm số bộ chỉ số (i1,i2,i3,j1,j2,j3) thỏa mãn đồng thời các điều kiện:

  • 1≤i1,i2,i3,j1,j2,j3≤n;
  • i1<i2<i3;
  • 6 chỉ số i1,i2,i3,j1,j2,j3 đôi một phân biệt;
  • Tam giác Pi1Pi2Pi3 không suy biến (nói cách khác, có diện tích dương);
  • △Pi1Pi2Pi3≅△Pj1Pj2Pj3.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n, số điểm đã cho.
  • n dòng tiếp theo, dòng thứ k chứa hai số nguyên xk và yk, tọa độ của điểm Pk.

Dữ liệu đảm bảo các điểm đã cho đôi một phân biệt.

Dữ liệu ra

In ra một số nguyên duy nhất là số bộ thỏa mãn tất cả các điều kiện trên.

Ràng buộc

  • 6≤n≤100.
  • 0≤|xk|,|yk|≤109.

Ví dụ

Input Output Giải thích
6
2 2
4 6
6 2
14 8
10 6
14 4
4 Tam giác P1P2P3 cân tại P2 (P1P2=P2P3) và bằng tam giác P4P5P6 cân tại P5. Bốn bộ hợp lệ là (1,2,3,4,5,6), (1,2,3,6,5,4), (4,5,6,1,2,3) và (4,5,6,3,2,1).
6
0 0
1 0
2 0
0 1
1 1
2 1
16 Ví dụ bổ sung (không có trong đề gốc). Chẳng hạn △P1P2P4≅△P6P5P3 (hai tam giác vuông cân có cạnh góc vuông bằng 1).

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