LCC/Moose '20 Contest 1 J5 - orz Alan

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.5s
Java 3.0s
PyPy 2 3.0s
PyPy 3 3.0s
Python 2 5.0s
Python 3 5.0s
Memory limit: 256M
Python 512M

Problem type

AlanL's friends are busy orzing him as AlanL is very orz. AlanL has N friends situated on the 2D plane, where each of his friends are located on a lattice point (point with integer-valued coordinates). Each of AlanL's friends is able to orz AlanL if he is on or inside a circle of radius R_i. Can you count how many lattice points AlanL can be on such that is he orz'd by at least one of his friends?

Input Specification

The first line will contain N\ (1 \le N \le 2 \times 10^3).

The next N lines will contain 3 integers x_i, y_i, R_i\ (0 \le x_i, y_i, \le 10^9), (1 \le R_i \le 2 \times 10^3), the coordinates and radius of AlanL's i^{th} friend.

Output Specification

Output the number of lattice points on one line.


Subtask 1 [20%]

(0 \le N, x_i, y_i, R_i \le 100)

(x_i, y_i \ge R_i)

Subtask 2 [30%]

(0 \le x_i, y_i \le 10^4)

Subtask 3 [50%]

No further constraints.

Sample Input

1 1 1
2 1 1
Sample Output


There are no comments at the moment.