Find the nearest point from 10 coordinates?

[emron]

Hello everybody,

Question 1: There are 10 houses in the neighborhood, the coordinates of the houses are given. A central building will be established in this neighborhood. In what position is this Central Building located close to all houses?

Question 2: According to him, if the center building to be established is 2 units, what are their positions?
(I use translator so maybe translate text is bad.)

Question1 my code:

#include <stdio.h>
#include <conio.h>

main()
{
	int x1=3,y1=5;
	int x2=7,y2=8;
	int x3=4,y3=1;
	int x4=9,y4=3;
	int x5=6,y5=2;
	int x6=13,y6=4;
	int x7=2,y7=12;
	int x8=3,y8=4;
	int x9=16,y9=12;
	int x10=7,y10=18;
	
	int koordinatx=(x1+x2+x3+x4+x5+x6+x7+x8+x9+x10)/10;
	int koordinaty=(y1+y2+y3+y4+y5+y6+y7+y8+y9+y10)/10;
		
	printf("Merkezin kurulmasi icin en uygun koordinatlar: %d,%d",koordinatx,koordinaty);
	
	
	getch();
}

Question 2 my code: (I am not sure)

#include <stdio.h>
#include <conio.h>

main()
{
	int x1=3,y1=5;
	int x2=7,y2=8;
	int x3=4,y3=1;
	int x4=9,y4=3;
	int x5=6,y5=2;
	int x6=13,y6=4;
	int x7=2,y7=12;
	int x8=3,y8=4;
	int x9=16,y9=12;
	int x10=7,y10=18;
	
	int koordinat1x=(x1+x2+x3+x4+x5)/5;
	int koordinat1y=(y1+y2+y3+y4+y5)/5;
	
	int koordinat2x=(x6+x7+x8+x9+x10)/5;
	int koordinat2y=(y6+y7+y8+y9+y10)/5;
	
		
	printf("1. Merkezin kurulmasi icin en uygun koordinatlar: %d,%d\n",koordinat1x,koordinat1y);
	printf("2. Merkezin kurulmasi icin en uygun koordinatlar: %d,%d",koordinat2x,koordinat2y);
	
	
	getch();
}

[dutch]

Wouldn't you just average the x's and y's?

[emron]

I thought so, too. I wanted to ask you. I don't want to do it wrong.

Another question: According to him, if the center building to be established is 2 units, what are their positions?

[Konstantin2]

For two units you have to check many combinations.
Combination #1:
Group #1 with points {1, 2, 3, 4, 5}, center at c₁,
Group #2 with points {6, 7, 8, 9, 10}, center at c₂.
c₁x = x₁ + x₂ + x₃ + x₄ + x₅;
c₂x = x₆ + x₇ + x₈ + x₉ + x₁₀;
c₁y = y₁ + y₂ + y₃ + y₄ + y₅;
c₂y = y₆ + x₇ + x₈ + x₉ + x₁₀;

Calculate sum of distances to the center in group #1
sum_len₁ = √((x₁ - c₁x)² + (y₁ - c₁y)²)
+ √((x₂ - c₁x)² + (y₂ - c₁y)²)
+ √((x₃ - c₁x)² + (y₃ - c₁y)²)
+ √((x₄ - c₁x)² + (y₄ - c₁y)²)
+ √((x₅ - c₁x)² + (y₅ - c₁y)²)

Calculate sum of distances to the center in group #2
sum_len₂ = √((x₆ - c₂x)² + (y₆ - c₂y)²)
+ √((x₇ - c₂x)² + (y₇ - c₂y)²)
+ √((x₈ - c₂x)² + (y₈ - c₂y)²)
+ √((x₉ - c₂x)² + (y₉ - c₂y)²)
+ √((x₁₀ - c₂x)² + (y₁₀ - c₂y)²)

Calculate total sum for combination #1
total_sum = sum_len₁ + sum_len₂

Combination #2:
Group #1 with points {1, 2, 3, 4, 6}, center at c₁,
Group #2 with points {5, 7, 8, 9, 10}, center at c₂.
c₁x = x₁ + x₂ + x₃ + x₄ + x₆;
c₂x = x₅ + x₇ + x₈ + x₉ + x₁₀;
c₁y = y₁ + y₂ + y₃ + y₄ + y₆;
c₂y = y₅ + x₇ + x₈ + x₉ + x₁₀;
…
Calculate total_sum for combination #2

Combination #3:
Group 1 with points {1, 2, 3, 4, 7}, center at c₁,
Group 2 with points {5, 6, 8, 9, 10}, center at c₂.
…
Calculate total_sum for combination #3

#4: {1, 2, 3, 4, 8}, {5, 6, 7, 9, 10}.
#5: {1, 2, 3, 4, 9}, {5, 6, 7, 8, 10}.
#6: {1, 2, 3, 4, 10}, {5, 6, 7, 8, 9}.
#7: {1, 2, 3, 5, 6}, {4, 7, 8, 9, 10}.
…
#12: {1, 2, 3, 6, 7}, {4, 5, 8, 9, 10}.
…
#22: {1, 2, 4, 5, 6}, {3, 7, 8, 9, 10}.
…
#30240: {6, 7, 8, 9, 10}, {1, 2, 3, 4, 5}.

Check every of 30240 combinations. Find where total_sum is minimal. That is your answer and your optimal 2 unit positions.

[helios]

Question 2 seems underspecified to me. What exactly is it that should be optimized? Right off the bat I can think of two things that someone might want to minimize:
1. For every house, the distance to the nearest Central Building (e.g. both CBs provide identical services that are required by all houses).
2. For every house, the sum of the distances to both CBs (e.g. one CB provides electricity and the other water, and it's desirable to minimize the amount of wires and plumbing).

[keskiverto]

There are more to ponder. The coordinates are integers.
If we have two houses, at 1 and 2, will the Center be build on 1.5? Platform to Hogwarts?
If the Center has to be on integer coordinate too, will it be build on top of existing building?


Q2 says "two units". Is that one building that covers two adjacent blocks, or two separate, standard-sized buildings?

For the "two separate centers" ... cluster analysis https://en.wikipedia.org/wiki/Cluster_analysis could give the two subsets houses for which one computes centres. That, however, sounds a bit too advanced.

[Browni3141]

Neither question 1 or 2 is very clear. How is "closeness" defined? I THINK that the mean of the x's and y's is optimal and unique if you are trying to minimize the average squared deviation from the mean, and also optimal but not necessarily unique if you are trying to minimize the average absolute deviation from the mean.

[mzimmers]

helios: I suspect the question being posed is closer to your #1. I think your #2 would be solved by co-locating the two CBs (unless you know of variations in the requirements of the individual houses).

The second question is somewhat malformed, but I assume that the goal is to reduce the total distance from all houses to one of the two CBs. There's no stated requirement that the CBs service the same number of houses, so even Konstantine's iteration example would be incomplete. I can't think of a way to bypass the brute force method for solving this one, but I imagine there must be another way.