c++ - Finding nearest point in an efficient way

Question

I've got a point in 2d plane for example (x0,y0) and a set of n points (x1,y1)...(xn,yn) and I want to find nearest point to (x0,y0) in a way better than trying all points. Any solutions?

I should also say that my points are sorted in this way:

bool less(point a,point b){
  if(a.x!=b.x)
     return a.x<b.x;
  else
     return a.y<b.y;
 }

Answer 1

Use a quad-tree for 2D http://en.wikipedia.org/wiki/Quadtree