Algorithm problem

[torayeff]

There is great problem in one of the algo contest sites. I am trying to solve it for 5 days. I am not asking you to solve me this for me, as I am new to algorithms I would like to ask you help me with classification of this type problem, did anyone solved problems like this, what is the type of problem NP or not. Please do not think that I am asking you to solve this for me, my purpose is just to learn algorithms and this is the problem which is enough difficult for me:

The goal of this puzzle is to determine where to place a set of gas stations so that they are closest to airports. Airports make use of a lot of gas for fueling planes, so placing gas stations close them is of strategical importance.

Input Specification Your program should take one and only one command line argument: the input file (passed in argv, args, arguments depending on the language). The input file is formatted as follows:

the first line contains an integer: n the number of airports the n following lines each contain 2 floating point values xi yi representing the coordinates of the ith airport the following line contains the number p of cases to analyze (p is always less than 5) the following p lines each contain one integer gi giving the number of required gas stations

Output Specifications: You program should output the result to the standard output (printf, print, echo, write): Your output should contain p lines, each line providing the gj coordinates xj,yj of the gas stations. Your solution score will be measured by the quality of the solution. The quality of the solution is measured by the total distance, the total distance D is the square root of the sum of squared distances from each airport to its closest gas station. The lower the total distance D, the higher your score will be.

[Zachm]

This is in fact a clustering problem - you wish to cluster n airports to gi groups where each group centroid is a gas station coordinate.
Simplest (but maybe not best) method is to use the K-means algorithm.

Kind regards,
Zachm

[torayeff]

Thank you very much for reference.