trang chủ / đề bài / icpc21_mb_g

Bao lồi bo tròn

Đề bài

Mô tả

Trên mặt phẳng tọa độ có N hình tròn và M đa giác. Hãy tính chu vi bao lồi của tất cả các hình này, tức là chu vi của hình lồi nhỏ nhất chứa toàn bộ các hình tròn và các đa giác.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên N và M (0≤N,M≤105, 1≤N+M): số hình tròn và số đa giác.
  • N dòng tiếp theo, mỗi dòng chứa ba số thực xi, yi và ri: tâm và bán kính của một hình tròn (|xi|,|yi|≤5×104, 0≤ri≤5×104).
  • M dòng tiếp theo, mỗi dòng bắt đầu bằng số nguyên pi (pi≥1) là số đỉnh của đa giác, tiếp theo là pi cặp số thực (xi,1,yi,1),…,(xi,pi,yi,pi) là tọa độ các đỉnh (|xi,j|,|yi,j|≤5×104). Tổng số đỉnh của tất cả các đa giác không vượt quá 105.

Dữ liệu ra

In ra chu vi của bao lồi. Kết quả được coi là đúng nếu sai số tuyệt đối hoặc sai số tương đối so với đáp án không vượt quá 10−5.

Ràng buộc

  • 0≤N,M≤105, 1≤N+M.
  • |xi|,|yi|≤5×104, 0≤ri≤5×104.
  • pi≥1, tổng các pi không vượt quá 105, |xi,j|,|yi,j|≤5×104.

Ví dụ

Input Output Giải thích
3 2
-14.123000 -1.456000 5.789000
0.123000 14.456000 4.789000
-6.868686 20.456780 3.789285
1 5.123000 5.456000
2 6.879000 6.123000 7.456000 7.789000
88.888888 Ba hình tròn, một đa giác chỉ có một đỉnh và một đa giác có hai đỉnh (một đoạn thẳng).
1 1
0.000000 0.000000 1.000000
1 2.000000 0.000000
7.652892 Ví dụ bổ sung (không có trong đề gốc). Bao lồi gồm hai tiếp tuyến từ điểm (2,0) tới đường tròn đơn vị, mỗi đoạn dài 3, và cung tròn 4π3: chu vi 23+4π3.

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