c - Algorithm to find shortest distance from a point in set A to points in set B -

-

there set n 3d points (x,y,z) , set b m 3d points (x,y,z). each point (xi,yi,zi) in set have find point in set b has minimum distance (xi,yi,zi).

my code running out of given time limit. please help.

#include<stdio.h> #include<stdlib.h> #include<math.h> long long np[50000][3],qp[50000][3]; int main() { long long n,q,i,j,d,ans,min; scanf("%lld",&n); for(i=0;i<n;i++)     scanf("%lld%lld%lld",&np[i][0],&np[i][0],&np[i][2]); scanf("%lld",&q); for(i=0;i<q;i++) scanf("%lld%lld%lld",&qp[i][0],&qp[i][1],&qp[i][2]); for(i=0;i<q;i++) {     ans=0;     min=((qp[i][0]-np[0][0])*(qp[i][0]-np[0][0]))+((qp[i][1]-np[0][1])*(qp[i][1]-qp[0][1]))+((qp[i][2]-np[0][2])*(qp[i][2]-np[0][2]));     for(j=0;j<n;j++)     {         d=((qp[i][0]-np[j][0])*(qp[i][0]-np[j][0]))+((qp[i][1]-np[j][1])*(qp[i][1]-qp[j][1]))+((qp[i][2]-np[j][2])*(qp[i][2]-np[j][2]));         if(d<min)         {             ans=j;             min=d;         }     }     printf("%lld\n",ans); } return 0; }

you're using o(n^2) algo. doubt fast enough. ways faster, check out this article.

or more specifically, can use divide conquer approach described in article, relatively straightforward if you're comfortable recursion. since dealing z axis, you'll have extend algo described there use 2 dividing lines (one x axis, 1 y), it's going bit more complicated.


Comments

Post a Comment

Popular posts from this blog

django - How can I change user group without delete record -

-
on website user have 1 group. , user can change group. it's made user.groups.clear() and user.groups.add(new_group) but it's not efficient, because there 2 sql query: delete, insert. how can change group update query? user , group related each other using manytomanyfield . means intersection table exists relating both entities, , if don't specify model map (using through attribute) django creates 1 you. looking @ sources django.contrib.auth.models see that's case. fortunatly, can access intermediary model using through attribute of manager (in case, user.groups.through ). can use regular model. example: >>> alice = user.objects.create_user('alice', 'alice@example.com', 'alicepw') >>> employee = group.objects.create(name='employee') >>> manager = group.objects.create(name='manager') >>> alice.groups.add(employee) >>> alice.groups.all() [<group: employee...
Read more

java - Need to add SOAP security token -

-
i need set custom soap header attribute on jax-ws generated webservice client. case webservice calls must go through proxy server requiring specific token (recieved web request header) present in soap request header. e.g.: 1 carserviceservice service = null; 2 service = new carserviceservice(new url(url), new qname(qname); 3 carserviceendpoint port = service.getcarserviceport(); it seems in line 3 wsdl retrieved , call fails due missing security token. 1 point direction on how done? a detailed example has been mentioned here: creating , deploying jax-ws web service on tomcat 6 this article shows how create , use security token .
Read more

java - EclipseLink JPA Object is not a known entity type -

-
i have strange problem eclipselink , object want persist. have 1 object (keypointlistimpl) stores object keypointimpl in list. persisting keypointimpl objects works great if try persist keypointlistimpl object java.lang.illegalargumentexception says object keypointimpl isn't known entity type. here keypointimpl code: @entity @table(name="keypoints") public class keypointimpl implements keypoint { @id @generatedvalue(strategy = generationtype.identity) private int id; @enumerated(enumtype.string) private detectortype keypointtype; private float x; private float y; private float size; private float angle; private float response; private int octave; private int classid; ... } here keypointlistimpl code: @entity @table(name="keypointlists") public class keypointlistimpl implements keypointlist { @id @generatedvalue(strategy = generationtype.identity) private int id; @onetoone(cascade={ca...
Read more