trang chủ / đề bài / icpcwf20_c

Những mái vòm

Đề bài

Mô tả

Nhà thờ Thánh Basil là công trình nổi tiếng nhất của Moskva, và có lẽ của cả nước Nga. Được xây dựng dưới thời Ivan Bạo chúa vào thế kỷ 16, nhà thờ nổi tiếng với những mái vòm đầy màu sắc. Chuyến thăm thành phố sẽ không trọn vẹn nếu thiếu một bức ảnh chụp nhà thờ trên Quảng trường Đỏ.

Hình 1: Hai góc nhìn của nhà thờ Thánh Basil.

Ban Du lịch Moskva (MTB) muốn giúp khách du lịch chụp được bức ảnh hoàn hảo về nhà thờ một cách an toàn nhất có thể. Tùy theo chỗ bạn đứng khi chụp, vị trí tương đối của các mái vòm trong ảnh sẽ khác nhau (xem Hình 1). MTB lo ngại rằng với một số cách sắp xếp mái vòm mong muốn, vùng trên Quảng trường Đỏ có thể chụp được bức ảnh như vậy sẽ nhỏ tới mức gây chen chúc nguy hiểm giữa các thợ ảnh. Để tránh cảnh xô đẩy, chấn thương và lây nhiễm Covid có thể xảy ra, MTB muốn tính diện tích vùng có thể chụp được ảnh với một thứ tự mái vòm mong muốn bất kỳ.

Để đơn giản, giả sử máy ảnh có góc nhìn 180 độ. Ví dụ, xét Hình 2, thể hiện vị trí các mái vòm (đánh số từ 1 tới 5) và người chụp ảnh (chấm màu xanh lá) trên mặt phẳng. Nếu người chụp hướng máy ảnh thẳng sang trái (nhắm thẳng vào mái vòm 5) thì mọi thứ trong vùng tô màu sẽ xuất hiện trong ảnh. Khi đó trong bức ảnh, các mái vòm xuất hiện theo thứ tự 4,3,5,2,1 từ trái sang phải.

Hình 2: Minh họa cho các ví dụ.

Cho vị trí các mái vòm trên Quảng trường Đỏ và thứ tự từ trái sang phải mong muốn của các mái vòm trong ảnh, MTB muốn biết diện tích vùng bên trong Quảng trường Đỏ mà từ đó có thể chụp được bức ảnh như vậy.

Có thể coi các mái vòm là các điểm, nên chúng không che khuất nhau, trừ khi chúng thẳng hàng với người chụp.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên dx, dy và n, trong đó dx và dy (2≤dx,dy≤105) là kích thước của Quảng trường Đỏ, còn n (1≤n≤100) là số mái vòm. Góc dưới bên trái của Quảng trường Đỏ ở gốc tọa độ (0,0) và góc trên bên phải ở tọa độ (dx,dy).

Mỗi dòng trong n dòng tiếp theo chứa hai số nguyên xi và yi (0<xi<dx, 0<yi<dy) là vị trí (xi,yi) của một mái vòm. Dòng thứ i mô tả mái vòm số i. Không có hai mái vòm nào ở cùng một vị trí.

Dòng cuối cùng chứa một hoán vị của các số {1,…,n}, cho biết thứ tự từ trái sang phải mong muốn của các mái vòm trong ảnh.

Dữ liệu ra

In ra diện tích của vùng bên trong Quảng trường Đỏ mà từ đó có thể chụp được bức ảnh có các mái vòm theo đúng thứ tự yêu cầu. Lưu ý diện tích có thể bằng 0 nếu không có vị trí nào chụp được bức ảnh như vậy. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không quá 10−3.

Ràng buộc

  • 2≤dx,dy≤105; 1≤n≤100.
  • 0<xi<dx, 0<yi<dy; các mái vòm đôi một khác vị trí.
  • Dòng cuối là một hoán vị của 1,2,…,n.

Ví dụ

Input Output Giải thích
100 100 5
30 70
50 60
50 40
30 30
20 50
4 3 5 2 1
450.000000 Hình 2: người chụp đứng ở chấm xanh lá, nhìn sang trái thấy các mái vòm theo thứ tự 4,3,5,2,1. Vùng chụp được là tam giác giới hạn bởi đường thẳng qua mái vòm 3 và 4, đường thẳng qua mái vòm 1 và 2, và cạnh phải x=100 của quảng trường, có diện tích 450.
100 100 5
30 70
50 60
50 40
30 30
20 50
1 2 5 4 3
0.000000 Cùng các mái vòm nhưng không có vị trí nào nhìn thấy chúng theo thứ tự 1,2,5,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