#include?
#include?
#include?
using?namespace?std;


struct?City//定義城市結構體
{
	int??coordinate;//某一維方向的城市坐標
	double?weight;//城市的權值
};


int?Get_pivot（City*?c?int?low?int?high?double&?leftsum?double&?rightsum）
{
	int?pivot?=?c[high].?coordinate;//設置樞軸值為最后一個數組的元素值
	int?i?=?low?-?1;//定義最終要得到的樞軸位置
	leftsum?=?0;//一開始的樞軸左邊的權值之和為0
	rightsum?=?0;//一開始的樞軸右邊的權值之和為0
	
	for?（int?j?=?low;?j?<=?high?-?1;?j++）//j指向第一個元素到倒數第二個元素進行循環
	{
		if?（c[j].?coordinate		{
			i++;//i指向要交換的較大元素位置
			//交換高低位置的元素，較大的數放右邊，較小的數放左邊
			City?temp?=?c[j];
			c[j]?=?c[i];
			c[i]?=?temp;
			//同時，左邊小于樞軸值的元素其權重累加求和
			leftsum?+=?c[i].weight;
		}
		else//如果該元素不小于最后一個數組的元素值
		{
			//右邊大于等于樞軸值的元素其權重累加求和
			rightsum?+=?c[j].weight;//這里，不需要交換元素，i不移動并在之后的某個循環中準備指向該較大元素的位置，并進行與之后j指向的較小值元素的交換
		}
	}
	//循環結束時，所有小于樞軸值的元素都在樞軸位置的左邊
	i++;//i指向最后不小于樞軸值的元素
	//將數組最后一個元素和i指向的不小于樞軸值的元素進行位置交換，這樣所有不小于樞軸值的元素就都在樞軸的右邊了
	City?temp?=?c[high];
	c[high]?=?c[i];
	c[i]?=?temp;
	//返回樞軸位置
	return?i;


}



//帶權中位數的查找
City?Get_Weighted_Median（City*?c?int?low?int?high?double?leftsummax?double?rightsummax）
{
	double?leftsum?rightsum;
	if?（low	{
		int?pivot?=?Get_pivot（c?low?high?leftsum?rightsum）;//得到樞軸的位置，以及按照樞軸位置排序的數組和樞軸左右各個元素的權值之和		
		if?（leftsum?			return?c[pivot];//返回該樞軸值
		else//否則
		{
			if?（leftsum?>=?leftsummax）//如果左邊的權值之和大于等于上界，說明帶權中位數在樞軸左側區間
			{
				rightsummax?=?rightsummax?-?rightsum?-?c[pivot].weight;//當前左側區間中的右側區間權值之和上限等于當前右側權值之和最大值減去右側權值之和再減去樞軸的權值
				return?Get_Weighted_Median（c?low?pivot?-?1?leftsummax?rightsummax）;//得到左側區間[lowpivot-1]的帶權中位數
			}
			else//如果右邊的權值之和大于上界，說明帶權中位數在樞軸右側區間
			{
				leftsummax?=?leftsummax?-?leftsum?-?c[pivot].weight;//當前右側區間中的左側區間權值之和上限等于當前左側權值之和最大值減去左側權值之和再減去樞軸的權值
				return?Get_Weighted_Median（c?pivot?+?1?high?leftsummax?rightsummax）;//得到右側區間[pivot+1high]的帶權中位數
			}
		}
	}
	//數組左右邊域數值相同則返回同時指向的元素
	return?c[low];
}

//顯示從文件中讀取的個城市坐標，并保存到輸出文件中
void?showCity（City?c_xCity?c_y）
{
	fstream?output;
	output.open（“Result.txt“?ios::app?|?ios::out）;
	output?<	cout?<	output?<	cout?<	output.close（）;
}
//將郵局位置結果保存到輸出文件中
void?ResultLocation（City?c_x?City?c_y）
{
	fstream?output;
	output.open（“Result.txt“?ios::app?|?ios::out）;
	output?<	cout?<	output?<	cout?<	output?<	cout?<	output.close（）;
}


int?main（int?argc?char**?argv）
{
	int?n?=?0;
	fstream?inputoutput_sigclear_txt;
	std::string?finput;
	std::string?assign1?=?“input_assign01_0“;
	std::string?assign2?=?“123456“;

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2019-03-13?16:10??分治法解決郵局選址問題?C++\
?????文件????????1899??2019-03-13?16:49??分治法解決郵局選址問題?C++\Readme.txt
?????文件?????????603??2018-10-12?20:12??分治法解決郵局選址問題?C++\Result.txt
?????文件?????????115??2018-10-05?23:08??分治法解決郵局選址問題?C++\input_assign01_01.dat
?????文件???????????9??2018-10-05?23:40??分治法解決郵局選址問題?C++\input_assign01_02.dat
?????文件??????????19??2018-10-05?23:40??分治法解決郵局選址問題?C++\input_assign01_03.dat
?????文件??????????33??2018-10-05?23:50??分治法解決郵局選址問題?C++\input_assign01_04.dat
?????文件??????????40??2018-10-05?23:49??分治法解決郵局選址問題?C++\input_assign01_05.dat
?????文件??????????51??2018-10-05?23:41??分治法解決郵局選址問題?C++\input_assign01_06.dat
?????文件????????5230??2018-10-06?15:18??分治法解決郵局選址問題?C++\main.cpp
?????文件??????117760??2018-10-06?15:18??分治法解決郵局選址問題?C++\postoffice.exe
?????文件??????693944??2018-10-06?15:18??分治法解決郵局選址問題?C++\postoffice.ilk
?????文件??????888832??2018-10-06?15:18??分治法解決郵局選址問題?C++\postoffice.pdb