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 độ. Ví dụ, xét Hình 2, thể hiện vị trí các mái vòm (đánh số từ tới ) 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 ) 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ự 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 , và , trong đó và () là kích thước của Quảng trường Đỏ, còn () là số mái vòm. Góc dưới bên trái của Quảng trường Đỏ ở gốc tọa độ và góc trên bên phải ở tọa độ .
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và (, ) là vị trí của một mái vòm. Dòng thứ mô tả mái vòm số . 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ố , 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 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á .
Ràng buộc
- ; .
- , ; 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 .
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ự . Vùng chụp được là tam giác giới hạn bởi đường thẳng qua mái vòm và , đường thẳng qua mái vòm và , và cạnh phải của quảng trường, có diện tích . |
| 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ự . |
Bình luận