/* //by Bell challenge by Cepagrave ANTS AND TREES - (coding challenge) You are the network designer of a colony of ants. Your colony just settled in a forest, and your job is to decide where to dig the holes/gates/entrances of your future underground network. The main food ressource for your species comes from the farming of aphids in trees. So you're given: - the 2D coordinates of all the farmable trees, - the number of gates that the colony can afford to secure, And you must decide: - the 2D coordinates where to start digging so that the total of the distances from each tree to its closest hole will be minimal. ex: trees = [(2,5),(3,7),(6,4),(7,2),(-5,1),(-4,3),(-2,1)] holes = 2 -> [[-3.667,1.667],[4.5,4.5]] trees = [(120,222),(645,-65),(668,566),(32,-99),(-7,65),(-230,-75),(147,-341)] holes = 3 -> [[-65.25,776.25],[12.4,-45.6],[634.5,266.25]] Initialize k means with (random) values For a given number of iterations: Iterate through items: Find the mean closest to the item Assign item to mean Update mean */ //kmeans from scratch #include #include #include #include #include #include #include using namespace std; class Point { public: double x; double y; }; double dist(Point p, Point q) { return std::sqrt((p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y));} void printP(Point p){ std::cout< trees= {{2.,5.},{3,7},{6.,4.},{7.,2.},{-5.,1.},{-4.,3.},{-2.,1.}}; vectorlabels={3,3,3,3,3,3,3}; int holes = 2,i,j=holes-1,l,li,k=1; double d=0.01, di; vector< Point > mu(holes); vector< int > clus(holes,0); for(i=0;id){mu[holes-1]=trees[i]; d=di; } } printP(mu[0]); printP(mu[1]); for(i=0;i<7;i++){ //update population l=(dist(trees[i],mu[0])0){ k=0; for(i=0;i<7;i++){ //update labels li=labels[i]; clus[li]--; l=(dist(trees[i],mu[0])

antsTrees