星星还是树
在二维平面上有 n 个点，第 i 个点的坐标为 (xi,yi)。 请你找出一个点，使得该点到这 n 个点的距离之和最小。 该点可以选择在平面中的任意位置，甚至与这 n 个点的位置重合。 输出最小距离和，答案四舍五入取整。原题链接
Example
4
0 0
0 10000
10000 10000
10000 0
题意： 就是找出一个点使得所有点的距离和最小。 使用三分法
代码
import java.util.*;
import java.io.*;
class Main {
static int[][] p;
public static double dist(double x1, double y1) {
double ret = 0.0;
for(int[] i : p) {
ret += Math.sqrt((i[0] - x1) * (i[0] - x1) + (i[1] - y1) * (i[1] - y1));
}
return ret;
}
public static double check(double x1) {
double l = 0.0, r = 10000.0;
while(r - l > 1e-4) {
double mid = (l + r) / 2;
double rmid = (mid + r) / 2;
if(dist(x1, mid) > dist(x1, rmid)) l = mid;
else r = rmid;
}
return dist(x1, l);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
p = new int[n][2];
for(int i = 0; i < n; i++) {
p[i][0] = scan.nextInt();
p[i][1] = scan.nextInt();
}
double l = 0.0, r = 10000.0;
while(r - l > 1e-4) {
double mid = (l + r) / 2;
double rmid = (mid + r) / 2;
if(check(mid) > check(rmid)) l = mid;
else r = rmid;
}
System.out.println((int)(check(l) + 0.5));
return;
}
}
代码2 选一个点，然后试图向8个方向移动。 注意8个方向的遍历
import java.util.*;
import java.io.*;
class Main {
static int[][] p;
static int R = 10000;
static double pi = Math.PI;
public static double dist(double x1, double y1) {
double ret = 0.0;
for(int[] i : p) {
ret += Math.sqrt((i[0] - x1) * (i[0] - x1) + (i[1] - y1) * (i[1] - y1));
}
return ret;
}
public static int solve(double x, double y) {
double ret = dist(x, y);
double rate = 0.6, step = rate * R;
double cx, cy;
double delta = pi / 4;
while(step > 1e-4) {
for(double theta = 0; theta < 2 * pi; theta += delta) {
cx = x + step * Math.cos(theta);
cy = y + step * Math.sin(theta);
double tmp = dist(cx, cy);
if(ret > tmp) {
x = cx;
y = cy;
ret = tmp;
}
}
step *= rate;
}
return (int)(ret + 0.5);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
p = new int[n][2];
double x = 0, y = 0;
for(int i = 0; i < n; i++) {
p[i][0] = scan.nextInt();
p[i][1] = scan.nextInt();
x += p[i][0];
y += p[i][1];
}
System.out.println(solve(x / n, y / n));
}
}