Problem E for Train 2
Задачу добавил: elena
Успешно сдано решений: 6
Problem E. Enormous spiral
Author: A. Klenin
Input file: input.txt Time limit: 3 sec
Output file: output.txt Memory limit: 64 Mb
Statement
Consider an infinite plane divided into square cells with the side of 1. The spiral starts at cell (0, 0) and consists of N straight segments. First segment runs from the starting cell in the direction of x axis, each following segment takes a 90° (pi/2) turn to the right. Segment number i contains exactly ai cells.
Segments do not overlap except at joint cells, which are treated as belonging to both adjacent segments.
A square window on the plane consists of S X S cells and is defined by coordinates of top left cell (x, y) (y axis is directed upwards).
Your program will be given coordinates of K square windows, and must determine, for each window, the number of cells inside it belonging to the spiral.
For example, a spiral below is defined by input of sample test 3. Cells marked with 'x' are inside the first window from the same test.
== pic E ==
Input file format
Input file contains numbers N K S followed by N integers ai, and then by K coordinates xi yi.
Output file format
Output file must contain K numbers — cell counts for each window.
Constraints
2 <= ai <= 10^9, a_(i-1) < a_(i+1), 1 <= N <= 10^6, -10^9 <= xi, yi <= 10^9, 1 <= K <= 10000, 1 <= S <= 100
Sample tests
Sample input 1
1 1 10
100
0 0
Sample output 1
10
Sample input 2
2 1 10
100 1000
1 -1
Sample output 2
0
Sample input 3
4 3 3
4 3 6 4
-1 0
0 0
1 0
Sample output 3
5 6 7