题目：给定一组二维点，每个点对应一个字符。给定任意一个位置，输出距离其最近点与它的距离。
输入
第一行两个数：点的个数N以及查询的个数M
接下来N行，每行2个浮点数和一个字符，代表点的坐标以及其对应的字符
接下来M行，每行2个浮点数，代表希望查询的位置
输出
M行，每行为点集中距离查询位置最近的距离，精确到小数点后4位。
代码：
#include
#include
#include
#include
#include
using namespace std;
struct data
{
double x;
double y;
};
struct Tnode
{
struct data dom_elt;
int split;
struct Tnode * left;
struct Tnode * right;
};
double ave(double a[],int n)
{
int sum=0;
for (int i=0;i<n;i++)
sum+=a[i];
return sum/n;
}
double variance (double a[],int n)
{
double sum=0;
double average=ave(a,n);//函数调用！！不许有【】！！！不许有int和double ！！
for (int i=0;i<n;i++)
sum=(a[i]-average)*(a[i]-average);
return sum/n;
}
bool cmp1(data a, data b){
return a.x < b.x;
}
bool cmp2(data a, data b){
return a.y < b.y;
}
bool equal(data a, data b){
if (a.x == b.x && a.y == b.y)
{
return true;
}
else{
return false;
}
}
void ChooseSplit(data exm_set[], int size, int &split, data &SplitChoice){
double tmp1,tmp2;
double v1,v2;
double flag1[size],flag2[size];
for(int i=0;i<size;i++){
flag1[i]=exm_set[i].x;
flag2[i]=exm_set[i].y;}
v1=variance(flag1,size);
v2=variance(flag2,size);
/*tmp1 = tmp2 = 0;
for (int i = 0; i < size; i++)
{
//while((double)size * exm_set[i].x * exm_set[i].x!=0&&(double)size * exm_set[i].x!=0)
tmp1 += 1.0 / (double)size * exm_set[i].x * exm_set[i].x;
tmp2 += 1.0 / (double)size * exm_set[i].x;
}
double v1 = tmp1 - tmp2 * tmp2;
tmp1 = tmp2 = 0;
for (int i = 0; i < size; i++)
{
//while((double)size * exm_set[i].x * exm_set[i].x!=0&&(double)size * exm_set[i].x!=0){
tmp1 += 1.0 / (double)size * exm_set[i].y * exm_set[i].y;
tmp2 += 1.0 / (double)size * exm_set[i].y;
///}
}
double v2 = tmp1 - tmp2 * tmp2;*/
split = v1 > v2 ? 1:0;
if (split == 0)
{
sort(exm_set,exm_set + size-1, cmp1);
}
else{
sort(exm_set,exm_set + size-1, cmp2);
}
SplitChoice.x = exm_set[size / 2].x;
SplitChoice.y = exm_set[size / 2].y;
}
Tnode* build_kdtree(data exm_set[], int size, Tnode* T){
if (size == 0){
return NULL;
}
else{
int split;
data dom_elt;
ChooseSplit(exm_set, size, split, dom_elt);
data exm_set_right [100];
data exm_set_left [100];
int sizeleft ,sizeright;
sizeleft = sizeright = 0;
if (split == 0)
{
for (int i = 0; i < size; i++)
{
if (!equal(exm_set[i],dom_elt) && exm_set[i].x <= dom_elt.x)
{
exm_set_left[sizeleft].x = exm_set[i].x;
exm_set_left[sizeleft].y = exm_set[i].y;
sizeleft++;
}
else if (!equal(exm_set[i],dom_elt) && exm_set[i].x > dom_elt.x)
{
exm_set_right[sizeright].x = exm_set[i].x;
exm_set_right[sizeright].y = exm_set[i].y;
sizeright++;
}
}
}
else{
for (int i = 0; i < size; i++)
{
if (!equal(exm_set[i],dom_elt) && exm_set[i].y <= dom_elt.y)
{
exm_set_left[sizeleft].x = exm_set[i].x;
exm_set_left[sizeleft].y = exm_set[i].y;
sizeleft++;
}
else if (!equal(exm_set[i],dom_elt) && exm_set[i].y > dom_elt.y)
{
exm_set_right[sizeright].x = exm_set[i].x;
exm_set_right[sizeright].y = exm_set[i].y;
sizeright++;
}
}
}
T = new Tnode;
T->dom_elt.x = dom_elt.x;
T->dom_elt.y = dom_elt.y;
T->split = split;
T->left = build_kdtree(exm_set_left, sizeleft, T->left);
T->right = build_kdtree(exm_set_right, sizeright, T->right);
return T;
}
}
double Distance(data a, data b){
double tmp = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
return sqrt(tmp);
}
void searchNearest(Tnode * Kd, data target, data &nearestpoint, double & distance){
stack search_path;
Tnode* pSearch = Kd;
data nearest;
double dist;
while(pSearch != NULL)
{
search_path.push(pSearch);
if (pSearch->split == 0)
{
if(target.x <= pSearch->dom_elt.x)
{
pSearch = pSearch->left;
}
else
{
pSearch = pSearch->right;
}
}
else{
if(target.y <= pSearch->dom_elt.y)
{
pSearch = pSearch->left;
}
else
{
pSearch = pSearch->right;
}
}
}
nearest.x = search_path.top()->dom_elt.x;
nearest.y = search_path.top()->dom_elt.y;
while(!search_path.empty()){search_path.pop();}
dist = Distance(nearest, target);
Tnode *pBack;
while(!search_path.empty())
{
pBack = search_path.top();
search_path.pop();
if(pBack->left == NULL && pBack->right == NULL)
{
if( Distance(nearest, target) > Distance(pBack->dom_elt, target) )
{
nearest = pBack->dom_elt;
dist = Distance(pBack->dom_elt, target);
}
}
else
{
int s = pBack->split;
if (s == 0)
{
if( fabs(pBack->dom_elt.x - target.x) < dist)
{
if( Distance(nearest, target) > Distance(pBack->dom_elt, target) )
{
nearest = pBack->dom_elt;
dist = Distance(pBack->dom_elt, target);
}
if(target.x <= pBack->dom_elt.x)
pSearch = pBack->right;
else
pSearch = pBack->left;
if(pSearch != NULL)
search_path.push(pSearch);
}
}
else {
if( fabs(pBack->dom_elt.y - target.y) < dist)
{
if( Distance(nearest, target) > Distance(pBack->dom_elt, target) )
{
nearest = pBack->dom_elt;
dist = Distance(pBack->dom_elt, target);
}
if(target.y <= pBack->dom_elt.y)
pSearch = pBack->right;
else
pSearch = pBack->left;
if(pSearch != NULL)
search_path.push(pSearch);
}
}
}
}
nearestpoint.x = nearest.x;
nearestpoint.y = nearest.y;
distance = dist;
}
int main(){
double x,y;
int m,n;
cin>>m>>n;
data exm_set[m];
char pos[m];
for(int i=0;i
{
cin>>x>>y;
cin>>pos[i];
exm_set[i].x = x;
exm_set[i].y = y;
}
struct Tnode *root = NULL;
root = build_kdtree(exm_set, m, root);
data nearestpoint;
double distance;
data target;
for(int j=0;j<n;j++)
{
double xx,yy;
cin>>xx>>yy;
target.x=xx;
target.y=yy;
searchNearest(root, target, nearestpoint, distance);
printf("%.4f\n", distance);
}
}
