Kattis - wheretolive 【数学】
Description
Moving to a new town can be difficult. Finding a good place to live which is close to everything you’re interested in is important. However, since you’re a great programmer, you know that you can solve this problem with an algorithm.
Everything in your virtualized town is laid out on a grid, so every place lies on an integer coordinate grid. You’ll be given a list of coordinates of the places you are interested in in the town, and you need to choose a place to live on the grid. Your program should find the grid location that minimizes the average straight-line squared distance to every place you are interested in (squared distance so that you won’t be too far from any one location).
You can live anywhere on the grid, even if something already exists where you want to live (buildings can always be built taller to accommodate you).
Input
Input consists of a list of up to 100
descriptions for towns you are considering moving to. Each town description starts with a line containing 1≤n≤1000, the number of locations you’re interested in. The next n lines each contain two space-separated integer coordinates x and y, each in the range [0,1000]. No location is repeated within a town. Input ends when n is 0
.
Output
For each town, print the location you want to live on the grid. If the best location is not exactly on a grid point, choose the grid point closest to the best location. Break ties by choosing the point that has the smallest x
coordinate and then the smallest y
coordinate.
Sample Input 1
5
82 25
25 16
97 59
38 38
15 21
9
51 13
33 2
8 46
64 25
13 40
39 75
17 42
14 6
3 43
0
Sample Output 1
51 32
27 32
题意
给出N个点的坐标，然后在这个平面内，求一个坐标使得所有点到这个坐标的距离平方和最小。
思路一
其实就是求质心。 质心就是 所有点的横坐标 求一个平均值，纵坐标求一个平均值，得出的两个值分别就是质心的横纵坐标。 为什么就是求质心呢。其实质点就是一个物体的重心。从物理上来说，就是一个物体重量最集中的地方。额 应该可以这么理解吧。那么N个点最集中的地方 大概就是质心了吧。。
但是最后如果求出来质心是一个浮点数，不能直接四舍五入。
比如 求出来是 51.4 31.8 不能直接四舍五入成 51 32 虽然这个例子 答案是对的 。但是一个正方形内某一个点到四个角的距离，哪个距离最短。。 还是四个距离都求一下 然后去最小吧。不能直接四舍五入。。
AC代码一
#include<iostream> //求质心
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const int MAX = 0x3f3f3f3f;
const int MIN = 0xc0c0c0c0;
const int maxn = 1e3 + 5;
double f(double x1, double y1, int x2, int y2)
{
x2 = (double)x2;
y2 = (double)y2;
return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main()
{
int x, y;
int n;
while (cin >> n && n)
{
double tot_x = 0, tot_y = 0;
int i, j;
for (i = 0; i < n; i++)
{
scanf("%d%d", &x, &y);
tot_x += x;
tot_y += y;
}
tot_x /= n;
tot_y /= n;
double dis = MAX;
double MAXN = MAX;
int a[2], b[2];
a[0] = floor(tot_x), b[0] = floor(tot_y), a[1] = ceil(tot_x), b[1] = ceil(tot_y);
for (i = 0; i < 2; i++)
{
for (j = 0; j < 2; j++)
{
dis = f(tot_x, tot_y, a[i], b[j]);
if (dis < MAXN)
{
MAXN = dis;
x = a[i];
y = b[j];
}
}
}
printf("%d %d\n", x, y);
}
}思路二
刚开始的做法 是想暴力枚举每一个点 因为平面范围是 [0, 1000]; 恭喜 TLE ；
然后后来想了想 因为是距离的平方和
距离公式 sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
距离的平方和 就是没有根号 就是 (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
因为没有根号 所以 X和Y 是可以单独拿出来枚举的
然后 就能A了。
AC代码二
#include<iostream> //不开平方 可以这样做
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define MAX 0x3f3f3f3f
#define MIN 0xc0c0c0c0
const int maxn = 1e3 + 5;
int x[maxn], y[maxn];
int main()
{
int n;
while (cin >> n && n)
{
double tot_x = 0, tot_y = 0;
int i, j;
int x_m[2], y_m[2];
x_m[0] = MAX;
x_m[1] = MIN;
y_m[0] = MAX;
y_m[1] = MIN;
for (i = 0; i < n; i++)
{
scanf("%d%d", &x[i], &y[i]);
if (x[i] < x_m[0])
x_m[0] = x[i];
if (x[i] > x_m[1])
x_m[1] = x[i];
if (y[i] < y_m[0])
y_m[0] = y[i];
if (y[i] > y_m[1])
y_m[1] = y[i];
}
int min_x = MAX, min_y = MAX;
int ans_x, ans_y;
for (i = x_m[0]; i <= x_m[1]; i++)
{
double dis = 0;
for (j = 0; j < n; j++)
{
dis += (x[j] - i) * (x[j] - i);
}
if (dis < min_x)
{
min_x = dis;
ans_x = i;
}
}
for (i = y_m[0]; i <= y_m[1]; i++)
{
double dis = 0;
for (j = 0; j < n; j++)
dis += (y[j] - i) * (y[j] - i);
if (dis < min_y)
{
min_y = dis;
ans_y = i;
}
}
printf("%d %d\n", ans_x, ans_y);
}
}