trang chủ / đề bài / snowblower

Máy thổi tuyết

Đề bài

Mô tả

Cho một đa giác n đỉnh trên mặt phẳng và một điểm P nằm ngoài đa giác (không nằm trong và không nằm trên biên). Đa giác được quay trọn một vòng quanh điểm P: mỗi điểm thuộc đa giác (kể cả các điểm trên biên) di chuyển trên một đường tròn tâm P.

Hãy tính diện tích vùng mặt phẳng mà đa giác quét qua trong quá trình quay.

Dữ liệu vào

  • Dòng đầu tiên gồm ba số nguyên n, px, py: số đỉnh của đa giác và tọa độ điểm P.
  • n dòng tiếp theo, mỗi dòng gồm hai số nguyên xi, yi: tọa độ các đỉnh của đa giác, liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.

Đa giác là đa giác đơn (có thể không lồi) và không có ba đỉnh liên tiếp nào thẳng hàng.

Dữ liệu ra

In ra một số thực là diện tích vùng bị quét. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá 10−6.

Ràng buộc

  • 3≤n≤105
  • |px|,|py|,|xi|,|yi|≤106
  • Điểm P nằm ngoài đa giác

Ví dụ

Input Output Giải thích
3 0 0
0 1
-1 2
1 2
12.5663706144 Điểm gần P nhất của tam giác là (0,1), cách P một khoảng 1; điểm xa nhất là (±1,2), cách P một khoảng 5. Vùng quét là hình vành khăn có diện tích π(5−1)=4π.
4 1 -1
0 0
1 2
2 0
1 1
21.9911485751 Đa giác không lồi. Điểm gần P nhất là (0,0) hoặc (2,0) với bình phương khoảng cách 2; điểm xa nhất là (1,2) với bình phương khoảng cách 9. Diện tích là π(9−2)=7π.

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