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);
}

}

0

1个回答

0
qq_40267093 谢谢~

Segmentation fault:段错误，检查是否有数组越界，指针异常，访问到不应该访问的内存区域
[code=c]#include rnusing namespace std;rn#define MAX 10000rnint main()rnrn int n, m;rn char a[MAX];rn char *p;rnrn cin>>n;rn for (int i=0; i>a[i];rn cin>>m;rnrn for (int i=0, j=n-m-1; i

void main()rnrn int a[1];rn a[2] = 2; // ok!rn int* p = a;rn *(p+2) = 2; // error!rnrnrn为什么有这样的不同！rn

Java内存区域与模拟内存区域异常

#include rn#include rnint main(void)rnrnchar *s="ab.de";rnchar *p;rnp=strchr(s,'.');rn*p='\0';rnprintf("%s\n", s);rnreturn 0;rnrnrn运行的时候 提示 段错误 rnrn如果将 char *s 改成 char s[] 就没有问题rnrn请讲解下原理 谢谢

void pp(char ** pstr)rnrn int i = 0, j = 0;rn while(pstr[i] != NULL)rn rn j = strlen(pstr[i]);rn rnrnrn对于越界的下标得到的元素值可能不是NULL，怎么检查呢？
【java】 Dubbo访问有时候访问到，有时候访问不到问题
Controller找server的时候有多个，这多个中只有95可以，当错误的时候就会对应的其他service的地方，下面报错的是157行，但是在本地的代码157行是注释，所以出现了这种诡异的情况。可以看出本地是192.168.21.95:61629，有两个提供者，其中一个是192.168.21.95:20881，另一个是192.168.22.165:20881。所以就出现了问题。解决方案之一是：在

rn如何检查指针是否赋值rnrn使用NEW 分配了个很大的指针数组,为了提高效率,不需要给不使用的元素赋值,当然没有初始化rnrnNEW 分配内存时,它会干些什么?rnrnrn当随机获取的时候,如何检查指针元素已经赋值rnrn使用 IF(指针) 可以吗?rnrn调式发现,没有初始化或赋值的指针值为 0xcdcdcdcdrnrn我想提高效率,免除不必要的赋值
delete是否检查指针类型？

linux下段错误检查sigsegv

Java内存区域与内存溢出异常
1、程序计数器： 1）、指令寄存器：寄存器是中央处理器内的组成部份。寄存器是有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和位址。指令寄存器（IR ）用来保存当前正在执行的一条指令。当执行一条指令时，先把它从内存取到数据寄存器（DR）中，然后再传送至IR。指令划分为操作码和地址码字段，由二进制数字组成。为了执行任何给定的指令，必须对操作码进行测试，以便识别所要求的操作。 2）、程序计数器...
java内存区域与内存溢出异常
1. 运行时数据区域1.1 方法区方法区是各个线程共享的内存区域，用于存储类的信息、常量。静态变量、即时编译器编译后的代码等数据,大小通过-XX:PermSize和-XX：MaxPermSize控制；还有一个别名为Non-Heap（非堆）和永久代。1.2 堆虚拟机启动时创建，是各个线程共享的内存区域，唯一目的就是存放对象实例，堆的大小通过-Xmx和-Xms控制，设置一样，即避免自动扩展，提高性能；还
JVM内存区域异常实战

JAVA内存区域与内存溢出异常
1，运行时数据区域 根据JAVA虚拟机规范的规定：JAVA虚拟机所管理的内存将会包括以下几个运行时数据区域     程序计数器（Program Counter Register）是一块较小的内存空间，它的作用可以看作是当前线程所执行的字节码的行号指示器，通过改变计数器的值来选取下一条需要执行的字节码指令、分支、循环、跳转、异常处理、线程恢复等基础功能。每条线程都需要一个独立的程序...

Ajax 访问到错误文件路径

class strn int a=0;rn static public void main(String args[])rn st qq=new st();rn // a=1;a=2;a=3;rn A s=new A();rn// System.out.println(a);rn cs e=new cs();rn rn rnclass csrnrn cs()rn System.out.println(A.b);rn oo();rn rnvoid oo()rn System.out.println(st.a);rn rnrnrnclass Arn static int b=10;rn
JVM内存区域异常模拟
JVM内存区域分为程序计数器，虚拟机栈，本地方法栈，堆区，方法区，运行时常量池以及本地直接内存。 程序计数器，每个线程都有一个独立的程序计数器，作为当前线程执行字节码的行号指示器。如果执行java方法则计数器记录正在执行的虚拟机字节码指令地址，如果执行native方法则该值为空。该区域不会发生OOM异常。 虚拟机栈，线程私有，java方法执行的内存模型。每个方法会创建一个栈帧，每执行一个方法对...
java内存区域与内存异常

【 Java 内存区域与内存溢出异常 】
1 概述 Java 程序员在虚拟机自动内存管理机制下，不再需要为每一个 new 操作去写配对的 delete/free 代码，不容易出现内存泄漏和内存溢出问题，由虚拟机管理内存看起来十分美好。 但是，一旦出现内存泄漏和溢出方面的问题，如果不了解虚拟机是怎么样使用内存的，那么排查错误将会十分艰难。 下面就介绍 Java 虚拟机内存的各个区域。 2 运行时的数据区域 Java 虚拟机在执行 Java ...

ext2.2 怎么访问到panel