### PROBLEM LINK:

**Author:** Alexandru Valeanu

**Editorialist:** Tiny Wong

### DIFFICULTY:

CHALLENGE.

### PREREQUISITES:

Greedy,

k-d tree.

### PROBLEM:

Given n points (x_i, y_i) with a collection of CPUs of processing time p_{ij}.

You are asked to answer q queries **ONLINE**. Each query contains a point (x, y), and you should associate it with an unused CPU, and the cost is \sqrt{(x-x_i)^2+(y-y_i)^2}+p_{ij}. Once a CPU of processing time p_{ij} is associated, it cannot be used until p_{ij} seconds passes.

### QUICK EXPLANATION:

There is a good enough greedy method, which is that we choose the minimal cost CPU that is unused currently.

### EXPLANATION:

In order to follow the greedy method declared in **QUICK EXPLANATION**, we can just use a k-d tree to find the nearest point.

More precisely, the CPUs are considered to be a 3-dimensional point (x_i, y_i, p_{ij}) with the meanings corresponding to the above, while each query point can be regarded as (x, y, 0). The distance between two points is defined by

Just following the simple idea can make you become a top coder of this problem.

### EDITORIALIST’S SOLUTION:

EDITORIALIST’s solution is here