11447 - Reservoir logs

A. Reservoir Logs

Background

在西班牙，缺乏雨水的問題相當嚴重。在 1970 年，年降雨量的減少被認為是造成水庫水位過低的原因，雖然全國各地的水庫平均容量少於 50%，但受災最嚴重的地區，如 Murcia (穆爾西亞) 水庫容量卻少於 20%

身為一個科學家，當降水進入水庫時要計算每個月的容量百分比。

The Problem

水庫的樣子被描述成一系列的點座標 (P[1], P[2], ..., P[N]) 定義為一個截面積(橫切面)，以及一個固定的寬 W，樣子約如下圖。給定的點一定是由左而右給，即 P[i].x <= P[i+1].x。

  水庫的橫切面:所有的尺寸座標都以公尺為單位。

我們知道水庫的水位高度 (以百分比表示)，同樣的我們也知道因蒸發和居民使用所消耗的水用量，以及落在水庫的降雨量(兩者的體積以立方公尺為單位)，假設水用量之發生在前半個月，而降於發生在後半個月(在同一個月，可能會發生缺水或過量水的情形)。

The Input

第一行會有一個整數 T (0 < T < 200) 表示接下來會有多少筆測資，每組測資間會有一個空白。

每組測資第一行會有一個整數 N (2 < N < 10000) 表示水庫座標 (x, y) 的個數 (x >= 0, y <= 0)，接下來會有 N 行，每行有兩個整數，表示座標的橫切面。第一個的座標和最後一個座標的 y = 0。所有座標將會由左而右給，而隨即會給一個整數 W 表示水庫的寬度。

最後會給定三個浮點數，第一個給定是水庫的水量百分比(相對於滿水位)，接著是消耗水量(單位立方公尺)，再者是降雨量(單位立方公尺)。

The Output

對於每組測資，最後輸出一行文字 "Final percentage: X%"，其中 X 表示最後的水量百分比，X 介於 0 到 100 (採無條件捨去)。如果水量消耗多於一開始給定的水庫量，輸出 "Lack of water. "在之後，如果最後水量多於水庫所能負荷的水量，則輸出 "Excess of water. " 最後才緊接著是輸出最後的百分比。

有可能三段文字都會出現，先缺水後被降雨補滿。

Sample Input

3

4
0 0
0 -2
2 -2
2 0
1
50.0 2.0 1.0

9
0 0
9 -2
11 -1
16 -3
22 -3
23 0
28 -2
28 -4
36 0
2
84.2 178.24 991.00

3
0 0
1 -1
2 0
100
0.01 23.00 49.99

Sample Output

Final percentage: 25%
Lack of water. Excess of water. Final percentage: 100%
Lack of water. Final percentage: 49%