Problem C. Covering the ring

Author:A. Baranov
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb

Statement

Let us consider a rectangular domain D = {(x, y): Ax ≤ x ≤ Bx, Ay ≤ y ≤ By} covered by the uniform grid (two-dimensional array of cells):

Ωi j = {(x, y): xi < x < xi+1, yj < y < yj+1}, where xi = Ax + (i − 1) ⋅ Sx, yj = Ay + (j − 1) ⋅ Sy, i = 1, 2, …, Nx, j = 1, 2, …, Ny,

Sx = (Bx − Ax) / Nx, Sy = (By − Ay) / Ny — grid steps for x and y respectively.

The grid is defined by four real parameters (Ax, Ay, Sx, Sy) and two integer parameters (Nx, Ny).

Note that cells are open rectangles not including their boundaries.

Your program must count grid cells that have common points with the ring defined by its center (x0, y0), internal and external radius (r1, r2).

Input file format

Input file contains parameters of the grid: Ax, Ay, Sx, Sy, Nx, Ny, followed by parameters of the ring: x0, y0, r1, r2.

Output file format

Output file must contain a single integer — number of cells intersecting the ring.

Constraints

All input values have no more than 5 digits after the decimal point.

− 10 < (Ax, Ay) < 10, 1 ≤ (Bx − Ax) < 10, 1 ≤ (By − Ay) < 10, 0 < (Nx, Ny) ≤ 106,

10 < (x0, y0) < 10, 0 ≤ r1 ≤ r2 < 10

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
-1.00000 -1.00000 0.12500 0.12500 16 16
 0.00000  0.00000 0.50000 0.90000
160
2
 0.00000  0.00000 0.05000 0.07143 20 14
 0.00000  0.00000 0.20000 0.74000
128

0.025s 0.006s 11