trang chủ / đề bài / icpc23_mt_m

Tam giác trong tam giác

Đề bài

Mô tả

Mười người giỏi tổ hợp hay quy hoạch động cũng không bằng một người giỏi hình học. (Tào Tháo không nói câu này)

Trên mặt phẳng tọa độ Oxy, cho tam giác không suy biến ABC. Nhiệm vụ của bạn là:

  1. Dựng tam giác đều PQR lớn nhất sao cho các đỉnh P, Q, R lần lượt nằm trên các đoạn thẳng AB, BC và CA.
  2. Dựng tam giác đều P′Q′R′ nhỏ nhất sao cho các đỉnh P′, Q′, R′ lần lượt nằm trên các đoạn thẳng AB, BC và CA.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test t (1≤t≤105).

Mỗi bộ test gồm một dòng chứa ba cặp số nguyên (xA,yA), (xB,yB), (xC,yC): tọa độ các đỉnh của tam giác ABC. Các đỉnh được liệt kê theo chiều ngược chiều kim đồng hồ.

Mọi tọa độ nằm trong đoạn [−103,103]. Dữ liệu đảm bảo tất cả các tam giác trong dữ liệu vào không suy biến.

Dữ liệu ra

Với mỗi bộ test, in ra hai số thực: độ dài cạnh của tam giác đều lớn nhất và của tam giác đều nhỏ nhất cần dựng.

Gọi p và P là độ dài cạnh của tam giác nhỏ nhất và lớn nhất mà bạn in ra, j và J là các giá trị tương ứng của ban giám khảo. Câu trả lời được coi là đúng nếu |p−j|max(1,j)≤10−9 và |P−J|max(1,J)≤10−9.

Ràng buộc

  • 1≤t≤105
  • −103≤xA,yA,xB,yB,xC,yC≤103
  • Tam giác ABC không suy biến, các đỉnh theo chiều ngược chiều kim đồng hồ.

Ví dụ

Input Output Giải thích
4
0 0 1 0 0 1
4 4 1 1 10 1
4 6 1 1 10 1
4 4 1 1 5 1
0.732050807569 0.517638090205
3.105828541230 2.477529576886
5.718776704299 3.493284678235
3.105828541230 1.834583397065
Với tam giác vuông cân A(0,0), B(1,0), C(0,1): tam giác đều lớn nhất có cạnh 3−1, tam giác đều nhỏ nhất có cạnh 6−22.
2
0 0 2 0 1 1
-1000 -1000 1000 -1000 0 1000
1.035276180410 0.732050807569
1945.220457180430 1071.796769724491
Hai tam giác cân với đáy AB.

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