trang chủ / đề bài / icpc24_reg_a

Bão đang đến

Đề bài

Mô tả

Aroma sống trên một hòn đảo giữa biển. Đang là mùa bão và Aroma cần chỉ đạo công tác dọn dẹp sau mỗi cơn bão, vì vậy cô muốn biết trước diện tích vùng bị ảnh hưởng bởi từng cơn bão.

Aroma mô hình hoá hòn đảo thành một đa giác đơn có n đỉnh và n cạnh. Đa giác có thể không lồi nhưng không tự cắt.

Có q cơn bão sắp tới. Mỗi cơn bão là một hình tròn di chuyển và có bán kính thay đổi. Cụ thể:

  • Cơn bão được mô hình hoá thành một hình tròn, tâm là mắt bão và bán kính là phạm vi ảnh hưởng.
  • Cơn bão xuất hiện với tâm tại điểm (xs,ys) và bán kính rs.
  • Tâm bão di chuyển dần theo đường thẳng từ (xs,ys) đến (xt,yt), đồng thời bán kính thay đổi dần từ rs đến rt. Chính xác hơn, tại một thời điểm, nếu khoảng cách từ tâm bão hiện tại đến (xs,ys) là ds và đến (xt,yt) là dt thì bán kính hiện tại của bão là ds·rt+dt·rsds+dt.
  • Khi tâm bão đến điểm (xt,yt), nó dừng ở đó cho đến khi tan.

Nếu tại một thời điểm nào đó, một điểm P trên đảo nằm trong hình tròn biểu diễn cơn bão thứ i thì P được gọi là bị ảnh hưởng bởi cơn bão này.

Hãy giúp Aroma tính diện tích phần đảo bị ảnh hưởng bởi mỗi cơn bão.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Dòng đầu tiên chứa số bộ test t (1≤t≤104). Mỗi bộ test có dạng:

  • Dòng đầu tiên chứa số nguyên n (3≤n≤3·105): số đỉnh của đa giác biểu diễn hòn đảo.
  • Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên xi, yi (|xi|,|yi|≤5000): toạ độ đỉnh thứ i của đa giác.
  • Dòng tiếp theo chứa số nguyên q (1≤q≤min(3·105,106n)): số cơn bão sắp tới.
  • Dòng thứ i trong q dòng tiếp theo chứa sáu số nguyên xs,ys,rs,xt,yt,rt (|xs|,|ys|,|xt|,|yt|≤5000, 1≤rs,rt≤100) mô tả cơn bão thứ i.

Dữ liệu đảm bảo:

  • các đỉnh được liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ;
  • không có hai đỉnh nào trùng toạ độ;
  • hai cạnh của đa giác chỉ giao nhau tại đỉnh chung của chúng (nếu có);
  • tổng n·q trên tất cả các bộ test không vượt quá 106.

Dữ liệu ra

Với mỗi cơn bão, in ra diện tích phần đảo bị ảnh hưởng trên một dòng. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá 10−6: gọi đáp án của bạn là a và đáp án của ban giám khảo là b, đáp án được chấp nhận khi và chỉ khi |a−b|max(1,|b|)≤10−6.

Ràng buộc

  • 1≤t≤104
  • 3≤n≤3·105, |xi|,|yi|≤5000
  • 1≤q≤min(3·105,106n)
  • |xs|,|ys|,|xt|,|yt|≤5000, 1≤rs,rt≤100
  • Tổng n·q trên tất cả các bộ test không vượt quá 106.

Ví dụ

Input Output Giải thích
3
3
0 0
0 3
4 0
5
0 0 4 0 0 4
0 0 1 0 3 1
0 0 2 4 0 2
1 1 1 5 5 5
-1 -1 1 3 3 3
5
0 0
1 1
2 2
2 0
2 -2
1
2 0 1 6 0 2
3
3 3
2 1
1 1
1
2 2 1 2 2 1
6.000000000000
2.625000000000
5.333333333333
5.785398163397
5.982317997582
1.576314961400
0.863647609001
Bộ test thứ nhất: hòn đảo là tam giác vuông có diện tích 6. Cơn bão thứ nhất đứng yên tại (0,0) với bán kính 4 nên phủ toàn bộ đảo. Cơn bão thứ hai quét một dải rộng 2 dọc trục tung từ (0,0) đến (0,3).
1
4
0 0
4 0
4 4
0 4
3
2 2 1 2 2 1
-2 2 1 6 2 1
2 2 100 2 2 1
3.141592654
8.000000000
16.000000000
Hòn đảo là hình vuông cạnh 4. Cơn bão thứ nhất đứng yên, ảnh hưởng một hình tròn bán kính 1 (diện tích π). Cơn bão thứ hai quét ngang dải 1≤y≤3 qua toàn bộ đảo (diện tích 8). Cơn bão thứ ba ban đầu đã phủ toàn bộ đảo.

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