Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBPIZZA - Cắt bánh pizza

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbpizza


Để 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. beo_chay_so 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 beo_chay_so 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 Xi, Yi 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.

Example

Input:
8 4
0 0
0 3
1 3
3 1
3 3
4 1
3 0
1 1
0
1
2
3

Output:
0.000000
4.000000
2.500000
1.000000

Giới hạn:
1 ≤ N ≤ 1000 
1 ≤ M ≤ 50000
Các tọa độ có trị tuyệt đối không quá 105 

Được gửi lên bởi:special_one
Ngày:2008-10-16
Thời gian chạy:0.300s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:HAOI

hide comments
2015-03-07 08:01:34 The Mastermind


Last edit: 2015-03-07 13:38:19
2012-12-10 15:19:58 ****** *** *****
Đa giác có lồi không vậy các bạn ? Nếu không lồi sao lại có các đỉnh liệt kê theo chiều kim đồng hồ nhỉ @_@

Last edit: 2012-12-10 15:20:39
2011-03-17 19:14:41 Tue Le


Last edit: 2011-03-17 19:19:34
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.