问题描述：
在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。要求：为建邮局选址，使得n个居民点到邮局之距离的总和最小。
提示：带权中位数（分治算法）题目分析：
（1）n个居民点散乱在街区中，是一个二维面，因此使用坐标来刻画每一个居民点；
这里的权值代表的是地点的重要程度或者是价值，比如医院、商场这样人流量大且重要的地点权值要高一些；
（2）不带权的中位数：就是一组有序数的中间值，如果为奇数为中间一个数，如果为偶数为中间两个数的平均值；
（3）带权中位数：就是给定的N个数都有一个权值，或者说相当于个数，然后求解
如何计算带权中位数：现将这些数按值排序，sum = (第i个数的权重 * 第i个数本身的值)
如果sum(k-1)= (第i个数的权重 * 第i个数本身的值) < sum/2
且 sum(k-1)= (第i个数的权重 * 第i个数本身的值) >= sum/2 ,则第k个元素为这组数的带权中位数
理解计算：之前已经说过权值其实可以看做是个数，也就是说如果X1=5，它的权值为3，X2=1，它的权值为5，先排序应该是X2,X1，然后再按公式计算。其实也就是把权值体现在个数上求中位数：1,1,1,1,1,5,5,5求这组数的中位数，上面的求前k-1个带权之和不就是展开后的求中位数么
（4）证明带权中位数是一维邮局位置问题的最佳解决方案
由此可以推出二维，只需转化成两个一维分别求取带权中位数即可，那么求出来的位置就是邮局所在的位置。
求解过程：
（1）从文件读取数据（数据包括x,y坐标以及两个坐标对应的权值）
（2）对x轴坐标排序，求取x方向的带权中位数；对y轴坐标排序，求取y方向的带权中位数（求取方法见上）
（3）两个带权中位数所组成的坐标就是邮局选址的位置
代码如下：
（1）居民点的实体类（本来想考虑实际意义进行封装，但是在后面的排序中发现考虑操作可能有些重复，也可以定义两个一维数组操作更方便）
public class Position {//位置实体类
private double x;//位置的横坐标
private double y;//位置的纵坐标
private double xWeight;//横坐标的权值
private double yWeight;//纵坐标的权值
//构造方法
public Position(){
}
//构造方法
public Position(double x, double xWeight, double y, double yWeight) {
this.x = x;
this.y = y;
this.xWeight = xWeight;
this.yWeight = yWeight;
}
//get/set方法
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
public double getxWeight() {
return xWeight;
}
public void setxWeight(double xWeight) {
this.xWeight = xWeight;
}
public double getyWeight() {
return yWeight;
}
public void setyWeight(double yWeight) {
this.yWeight = yWeight;
}
@Override
public String toString() {
return "Position{" +
"x=" + x +
", y=" + y +
", xWeight=" + xWeight +
", yWeight=" + yWeight +
'}';
}
}
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Test {
public static void main(String[] args) throws IOException {
System.out.println("请输入要测试的数据序号：");
Scanner input = new Scanner(System.in);
int num = input.nextInt();
//从文件读取数据并对其进行封装
List list = readData(".\input_assign01_0"+num+".dat");
System.out.println(list.toString());
//调用方法求取邮局坐标
Position pos = postOffice(list);
System.out.println("x:"+pos.getX()+"ny:"+pos.getY());
}
public static List readData(String path) throws IOException {
List list = new ArrayList<>();
//打开输入流
InputStream is = new FileInputStream(path);
BufferedReader reader = new BufferedReader(new InputStreamReader(is));
String buffer = null;
while ((buffer = reader.readLine())!=null){//按行读取
String[] str = buffer.split("，");
Position pos = new Position(Double.parseDouble(str[0]),Double.parseDouble(str[1]),Double.parseDouble(str[2]),Double.parseDouble(str[3]));
list.add(pos);
}
//关闭流
is.close();
reader.close();
return list;
}
public static List qSort(List list, int low, int height, String choose){
if(low>=height){//判断位置的合法性
return list;
}
Position temp = list.get(low);//先选择一个位置
Position change = null;
int i = low;//i指针从低到高筛选
int j = height;//j指针从高到低筛选
//当对x轴的权值进行排序时
if(choose.equals("x")){
while(i!=j){
while(list.get(j).getX()>=temp.getX() && i=temp.getY() && i list){
Position postOffice = new Position();
double xsum = 0;//用来记录x轴的权重之和
double ysum = 0;//用来记录y轴的权重之和
double sum = 0;
List xlist = qSort(list,0,list.size()-1,"x");//对x坐标进行由小到大排序
// System.out.println("x:"+xlist.toString());
//分别计算x轴和y轴的权重之和
for(int i=0;i xsum/2){//累加的权值之和刚好大于权值总和的一半时，所对应的x值为带权中位数
postOffice.setX(xlist.get(j).getX());
break;
}
}
//对y坐标进行由小到大排序
List ylist = qSort(list,0,list.size()-1,"y");
// System.out.println("y:"+ylist.toString());
sum = 0;
//求y轴的带权中位数作为邮局的纵坐标
for(int k=0;k ysum/2){
postOffice.setY(ylist.get(k).getY());
break;
}
}
return postOffice;
}
}
输入数据存储格式：
分别代表x坐标，x的权值，y坐标，y权值。每一行代表一个居民点
