# -*- coding: utf-8 -*-
import sys
import numpy as np
import os
#快速排序算法函数
def Partition(low, high, a, w):
#确定轴点
x = a[low]
wmid = w[low]
while(low < high):
while(a[high] > x and low < high):
high -= 1
a[low] = a[high] #将比轴点小的数移至左端
w[low] = w[high] #将比轴点小的数的权值移至左端
while(a[low] <= x and low < high):
low += 1
a[high] = a[low] #将比轴点大的数移到右端
w[high] = w[low] #将比轴点大的数的权值移至右端
a[low] = x #low==high，low位为空，填入轴点数x
w[low] = wmid #填入轴点的权值
return low #返回排序的中间位置
#分治思想实现快速排序
def QuickSort(low, high, a, w):
if (low < high):
mid = Partition(low, high, a, w) #一次排序并找到分治中值
QuickSort(low, mid - 1, a, w)
QuickSort(mid + 1, high, a, w)
#得到加权中位值
def GetMidWeight(low, high, sw, w):
midSum = 0.0 #初始化加权值计算
for i in range(low, high): #循环计算加权值，得到加权中位值的位置
midSum += w[i] #当前加权值求和
if(midSum >= sw / 2): #比较是否加至加权中位值
return i #返回满足加权中位值的坐标值
#得到距离值
def getDistance(n, x, y, wx, wy, sw):
dx = 0 #初始化x坐标中位数所在数组中的位置
dy = 0 #初始化y坐标中位数所在数组中的位置
Distance = 0 #初始化距离值
QuickSort(0, n - 1, x, wx) #对x坐标值进行快速排序
dx = GetMidWeight(0, n - 1, sw, wx)
QuickSort(0, n - 1, y, wy) #对y坐标值进行快速排序
dy = GetMidWeight(0, n - 1, sw, wy)
print('排序后的横纵坐标：')
print('x wx y wy')
for i in range(n):
print(x[i], wx[i], y[i], wy[i])
print('邮局选址坐标为:')
print('x y')
print(x[dx], y[dy]) #输出使得距离最短的邮局选址坐标
#循环计算最短距离
for i in range(n):
Distance += abs(x[i] - x[dx]) + abs(y[i] - y[dy])
print('最小距离和为:')
print(Distance) #输出最短距离
#需要测试的五组数据所在文件夹
file_name = ['input_assgin01_01.dat', 'input_assgin01_02.dat','input_assgin01_03.dat',
'input_assgin01_04.dat', 'input_assgin01_05.dat']
#循环读取五组文件内容
for file_name in file_name:
print ('##########################')
print ('{0}文件中的测试结果：'.format(file_name))
a = np.loadtxt(file_name) #读取存数文档
n = int( a[0][0] ) #读取小区数目
print('小区数目为：')
print(n) #输出小区数目
x = [0] * n #初始化各小区的横坐标存储数组
y = [0] * n #初始化各小区的纵坐标存储数组
wx = [0.0] * n #初始化小区横坐标的加权值
wy = [0.0] * n #初始化小区纵坐标的加权值
sw = 0.0 #初始化加权值和
print('各小区的位置坐标以及加权值：')
print('x y wx wy')
a = np.loadtxt(file_name, skiprows = 1, dtype = int) #读取存数文档中除第一排的数据
for i in range(n): #循环读取各个小区的横纵坐标
x[i] = int( a[i][0] ) #循环读取横坐标
y[i] = int( a[i][1] ) #循环读取纵坐标
wx[i] = float( a[i][2] ) #循环读取坐标加权值
wy[i] = wx[i] #将y坐标加权值赋值，与x坐标的加权值一致
sw +=wx[i] #计算坐标加权值和，用以之后计算加权中位数
print(x[i], y[i], wx[i], wy[i]) #输出各小区的位置坐标
print('小区的加权值和：\n',sw)
getDistance(n, x, y, wx, wy, sw) #调用计算最短距离的函数
os.system('pause')
