VOI 22 Bài 5 - Phần mềm vẽ

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: PAINT.INP
Output: PAINT.OUT

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Nam đã xây dựng được một phần mềm vẽ hình với giao diện chính là một bảng vẽ kích thước ~W \times H~. Bảng vẽ được đặt trên hệ trục chiếm một vùng là một hình chữ nhật có tọa độ trái dưới là ~(0, 0)~ và tọa độ phải trên là ~(W, H)~. Nam đã vẽ ~n~ đa giác lỗi trên bảng vẽ để thử nghiệm phần mềm, đa giác nào cũng có đúng ~m~ đỉnh.

Đa giác thứ ~i~ (~1 \le i \le n~) được mô tả bằng dãy tọa độ của ~m~ đỉnh liệt kê theo chiều kim đồng hồ tương ứng là ~(x_{i, 1}, y_{i, 1}), (x_{i, 2}, y_{i, 2}), \ldots, (x_{i, m}, y_{i, m})~. Hai cạnh bất kì của hai đa giác không có điểm chung và cũng không chạm vào biên của bảng vẽ. Có ~Q~ phương án thử nghiệm, phương án thứ ~t~ (~1 \le t \le Q~) sẽ thực hiện bấm tô màu vào điểm ~(x_t, y_t)~ không nằm trên bất kì cạnh cào của đa giác cũng như biên của bảng vẽ, khi đó toàn bộ vùng chứa điểm ~(x_t, y_t)~ được giới hạn bởi các cạnh của đa giác và biên của bảng vẽ sẽ được tô, phần mềm sẽ trả về diện tích vùng được tô.

Yêu cầu: Cho ~n~ đa giác lồi cùng có ~m~ đỉnh và ~Q~ phương án tô màu, với mỗi phương án hãy xác định diện tích vùng được tô màu để kiểm tra phần mềm.

Dữ liệu

Vào từ file văn bản PAINT.INP:

  • Dòng đầu chứa năm số nguyên ~W, H, n, m, Q~ (~W, H \le 10^8; 3 \le m \le 5~);
  • Dòng thứ ~i~ (~1 \le i \le n~) trong ~n~ dòng tiếp theo chứa ~2m~ số nguyên dương ~x_{i, 1}, y_{i, 1}, x_{i, 2}, y_{i, 2}, \ldots, x_{i, m}, y_{i, m}~ lần lượt là tọa độ ~m~ đỉnh được liệt kê theo chiều kim đồng hồ của đa giác thứ ~i~ (~0 < x_{i, 1}, x_{i, 2}, \ldots, x_{i, m} < W~; ~0 < y_{i, 1}, y_{i, 2}, \ldots, y_{i, m} < H~);
  • Dòng thứ ~t~ (~1 \le t \le Q~) trong ~Q~ dòng tiếp theo chứa hai số nguyên dương ~x_t, y_t~ mô tả phương án thứ ~t~ (~0 < x_t < W~; ~0 < y_t < H~).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra file văn bản PAINT.OUT gồm ~Q~ dòng, mỗi dòng chứa một số thực (lấy đúng một chữ số sau dấu chấm thập phân) là diện tích vùng được tô tương ứng phương án trong dữ liệu vào.

Ràng buộc

  • Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thỏa mãn: ~n, Q \le 20~ và các đa giác là các hình chữ nhật có cạnh song song với một trong hai trục tọa độ;
  • ~35\%~ số test khác ứng với ~35\%~ số điểm của bài thỏa mãn: ~n, Q \le 2000~;
  • ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thỏa mãn: ~n, Q \le 10^5~ và các đa giác là các hình chữ nhật có cạnh song song với một trong hai trục tọa độ;
  • ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài thỏa mãn: ~n, Q \le 10^5~.

Ví dụ

Input
9 8 4 3 3
8 1 1 1 1 7
5 7 8 7 8 5
2 3 2 5 3 4
2 2 4 3 5 2
7 6
6 2
8 3
Output
3.0
18.5
48.0
Minh họa


Comments

Please read the guidelines before commenting.


There are no comments at the moment.