Cắt bánh pizza

View as PDF

Submit solution

Points: 1.74 (partial)
Time limit: 0.45s
Memory limit: 512M
Input: stdin
Output: stdout

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

Để chuẩn bị cho buổi giao lưu của cuộc thi HAOI năm nay, msn và Lola đã mua về một chiếc bánh pizza có hình thù đặc biệt. Chiếc bánh là một hình đa giác ~N~ đỉnh không tự cắt.

BB được giao nhiệm vụ sẽ cắt chiếc bánh này để chia cho mọi người. Để tăng thêm sự thú vị cho buổi giao lưu, BB đưa ra bài toán sau cho các bạn thí sinh. Nếu ta đặt chiếc bánh vào hệ tọa độ Đề các, mỗi nhát cắt sẽ là một đường thẳng song song với trục hoành.

BB muốn biết với mỗi nhát cắt như vậy, tổng độ dài của nhát cắt đi qua chiếc bánh là bao nhiêu. Một nhát cắt nếu đi trùng vào một cạnh của chiếc bánh phải tính cả độ dài của cạnh đó (xem trường hợp nhát cắt ~y = 3~ trong test ví dụ). Người trả lời đúng nhiều nhất nhận được phần bánh to nhất, nhiều pho mát nhất, nhiều thịt bò nhất. beochayso vốn rất ham ăn và rất muốn có phần bánh ngon nhất đó. Bạn hãy giúp beochayso nhé.

Input

Dòng đầu tiên là hai số nguyên dương ~N~ và ~M~ trong đó ~M~ là số nhát cắt sẽ thực hiện.

Dòng thứ ~i~ trong ~N~ dòng tiếp theo ghi hai số nguyên ~X_{i}~, ~Y_{i}~ là tọa độ của đỉnh thứ ~i~ của chiếc bánh.

Tọa độ đỉnh của chiếc bánh sẽ được liệt kê theo chiều kim đồng hồ.

Trên ~M~ dòng cuối, mỗi dòng có một số nguyên alpha trong đó đường thẳng ~y =~ alpha là đường thẳng thể hiện nhát cắt.

Output

Tương ứng với ~M~ dòng trong input, hãy ghi ra ~M~ số trên ~M~ dòng thể hiện tổng độ dài của nhát cắt thứ ~i~ đi qua chiếc bánh. Các số được ghi với độ chính xác ít nhất ~6~ chữ số sau dấu phẩy.

Giới hạn

~1 \leq N \leq 1000~

~1 \leq M \leq 50000~

Các tọa độ có trị tuyệt đối không quá ~10^{5}~

Sample Input

8 4
0 0
0 3
1 3
3 1
3 3
4 1
3 0
1 1
0
1
2
3

Sample Output

0.000000
4.000000
2.500000
1.000000

Comments

Please read the guidelines before commenting.


There are no comments at the moment.