trang chủ / đề bài / icpcwf13_j

Giải pháp ô nhiễm

Đề bài

Mô tả

Là nhân viên của công ty Aqueous Contaminate Management, bạn phải theo dõi lượng chất ô nhiễm bị đổ (đôi khi vô tình, đôi khi cố ý) xuống sông, hồ và biển. Một trong các nhiệm vụ của bạn là đo mức độ ảnh hưởng của ô nhiễm lên các hệ sinh thái dưới nước như rạn san hô, bãi đẻ trứng, v.v.

Mô hình phân tích được minh họa trong hình trên (ứng với ví dụ thứ nhất). Bờ biển (đường nằm ngang trong hình) nằm trên trục x, nguồn ô nhiễm đặt tại gốc tọa độ (0,0). Vùng ô nhiễm lan ra mặt nước được biểu diễn bằng nửa hình tròn tâm tại gốc tọa độ, bán kính r, nằm phía trên trục x; còn đa giác biểu diễn hệ sinh thái cần quan tâm. Bạn cần tính diện tích phần hệ sinh thái bị ô nhiễm, tức là phần được tô màu xanh đậm trong hình.

Dữ liệu vào

Dữ liệu gồm một bộ test duy nhất. Dòng đầu tiên chứa hai số nguyên n và r, lần lượt là số đỉnh của đa giác và bán kính của vùng ô nhiễm. Tiếp theo là n dòng, dòng thứ i chứa hai số nguyên xi,yi là tọa độ đỉnh thứ i của đa giác, các đỉnh được liệt kê theo thứ tự ngược chiều kim đồng hồ.

Dữ liệu ra

In ra diện tích phần đa giác nằm trong nửa hình tròn tâm tại gốc tọa độ, bán kính r. Đáp án được chấp nhận nếu sai số tuyệt đối không vượt quá 10−3.

Ràng buộc

  • 3≤n≤100.
  • 1≤r≤1000.
  • −1500≤xi≤1500, 0≤yi≤1500.
  • Đa giác không tự cắt và không tự chạm.
  • Không có đỉnh nào nằm trên đường tròn biên.

Ví dụ

Input Output Giải thích
6 10
-8 2
8 2
8 14
0 14
0 6
-8 14
101.576437872 Đa giác và nửa hình tròn như trong hình, phần bị ô nhiễm là vùng tô màu.
3 5
0 0
7 1
-1 7
19.634954085 Cạnh từ (7,1) tới (−1,7) tiếp xúc với đường tròn tại (3,4), nên phần bị ô nhiễm là hình quạt góc vuông giữa hai cạnh xuất phát từ gốc tọa độ: diện tích 25π4≈19.635.

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