大侠帮忙！万分感谢

问题一：
        给定一组随即点的纵横坐标(x[i],y[i]),再给定一个点P，计算P到这组点的最近距离，也就是求一个点Q，
        使得P到其他所有点的距离都不小于P到Q的距离，主要是计算的速度，挨个查询效率很低。
问题二：给一组折线断和一个点P，计算P到这组线段的最近距离，也就是求一段线段和这段线段上的一个点Q。
        使得P到其他线段上的点的距离都不小于P到Q的距离，并求出这段线段的起点到Q的距离
小弟不知如何优化，查询是太慢了，请指教！！！

7 个解决方案

#1

找个数学好的人来做吧，我是不行了

#2

查询已经是O(n)了，还不够你牛b的？

#3

随机的点的话，遍历是没法避免的。能优化的只有不要用sqrt取平方根，直接算出平方矩离就行了，因为你只是比较大小。sqrt很费时

建议楼主贴代码看看有没有好优化的

#4

一组随即点，又没规律，好像只能查询了。

限制效率的是2点距离的计算，不过运算量也不大。

#5

楼上的说的对，如果没有规律，好像真的只有遍历了。

#6

不好意思
好像应该是θ(n)

#7

typedef struct coordinate
{
  double x_cd;
  double y_cd;
}* Point;/*Using a struct with two members 'x_cd' and 'y_cd' to descripe a point  */
struct Line
{
coordinate StartPoint;
coordinate EndPoint;
};
#define MAXSIZE 10000/* Maximum number of points*/
#define MAXDISTANCE 100000/*maximum distance between points */
#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;
Point Read_data_from(char* filename);/*read coordinate of points from finame and store it in 
array PointsArray ,then return the address of the array*/
double Min_dis(Point PointsArray,coordinate KeyPoint);/*Calculate the distance between point 'Keypoint' and the other points,
then return the index of the point who is the nearest point to KeyPoint,meanwhile store the  minimum diatance
in the  first position of the array as PointsArray[0].y_cd */
int main(int argc,char*argv[])
{
   coordinate KeyPoint;
   coordinate* Points=Read_data_from("data.txt");/*read data from file and store it in the array */ 
   int size=(Points[0].x_cd--);/*Get the size  of  Point array */
   KeyPoint=Points[size];/*Read the keypoint lastly */
   cout<<Min_dis(Points,KeyPoint)<<endl;
   cout<<Points[0].y_cd<<endl;
   return 0;
}
/***********************************************************************************************************/
Point Read_data_from(char *finame)
{
      ifstream read(finame);
  if(read==NULL)
  {
    cout<<"Error,file not exist\n";
    exit(1);
  }/*If the file can not be opened ,end the programe*/
  int counter(0);/*To count the number of points read in*/
  Point  PointsArray=new coordinate[MAXSIZE];
      while(read>>PointsArray[counter+1].x_cd && read>>PointsArray[counter+1].y_cd)
    counter++;
  PointsArray[0].x_cd=counter;/*We use the first position to store the number of points */
  return PointsArray;
}
/*************************************************************************************************************/
double Min_dis(Point PointsArray,coordinate KeyPoint)
{
    const length=PointsArray[0].x_cd;/*Get the size of array*/
double x=KeyPoint.x_cd,y=KeyPoint.y_cd;
int index(0);/* the number of the nearest point */
double MinDistance(MAXDISTANCE);/*initailize the minmun distance with a big number */
for(int i=1;i<=length;i++)/*Loop to calculate every distance*/
{
    double temX=PointsArray[i].x_cd;
double temY=PointsArray[i].y_cd;
double dis=sqrt((x-temX)*(x-temX)+(y-temY)*(y-temY)); 
MinDistance= MinDistance > dis ? dis : MinDistance;/*if new distance is small than MinDistance,change
MinDistance with new distance 'dis',and then change the index of the nearest point */
index= MinDistance >= dis ? i:index; 
}
PointsArray[0].y_cd=index;
return MinDistance;/*store the  index of the nearest point as PointsArray[0].y_cd*/
}
这是我写的，但是从点的平面分布来说，可能有以下的优化方法：
比如：把平面划分成若干区域，应最先在已知点的最近邻近区域内找，找到了当然最近。
还有，就是以已知点为圆心搜索其周围，最先找到的应该为最优解，但是我不好实现！
还请各位指点一二，万分感谢！！！