import?java.io.BufferedInputStream;
import?java.io.FileInputStream;
import?java.io.FileNotFoundException;

import?java.io.FileWriter;
import?java.io.IOException;
import?java.util.Scanner;
public?class?postoffice?{
	int?number;//該數(shù)據(jù)文件中坐標點個數(shù)
	long??result;//最終結果
	long?temp;//用來保存中間變量

	int?bigx;//最西
	int?bigy;//最北
	int?smallx;//最東
	int?smally;//最南
	
	
	int?a[];//數(shù)組用來存儲東西坐標值
	int?b[];//數(shù)組用來存儲南北坐標值
	/**
	?*?該方法完成輸入輸出并調(diào)用算法實現(xiàn)方法
	?*/
	public?void?dojob（）{
		
		try?{
			FileWriter?fw?=?new?FileWriter（“output.txt“）;
			
			for（int?m=0;m<11;m++）{
			result?=Long.MAX_VALUE;
			Scanner?in;
			//從文件中讀取數(shù)據(jù)初始化坐標數(shù)組（一共11組測試數(shù)據(jù)）
			if（m==10）
				in?=?new?Scanner（new?BufferedInputStream（new?FileInputStream（“input_assign01_“+?m?+“.dat“）））;
			else
				in?=?new?Scanner（new?BufferedInputStream（new?FileInputStream（“input_assign01_0“+?m?+“.dat“）））;
			
			number?=?in.nextInt（）;
			a=new?int[number];
			b=new?int[number];
			for（int?i=0;i			{
				a[i]=in.nextInt（）;
				b[i]=in.nextInt（）;
			}
			//遍歷數(shù)組得到東西南北坐標極值
			smallx?=a[0];?bigx=a[0];
			smally?=b[0];?bigy?=b[0];
			for（int?i=1;i			{	
				if（a[i]				else?if（a[i]>bigx）?bigx?=a[i];
				if（b[i]				else?if（b[i]>bigy）?bigy?=b[i];
				
			}
			//調(diào)用算法實現(xiàn)方法得到最佳點郵局與所有居民點距離之和
			result?=?findbest（a?smallx?bigx）?+?findbest（b?smally?bigy）;
			//將結果輸出到文件中
			fw.write（result+““）;
			fw.write（“\r\n“）;
			fw.flush（）;
			//將結果輸出到屏幕
			System.out.println（m?+?“:“?+?result）;
			
			
			}
		}?catch?（FileNotFoundException?e）?{
			//?TODO?Auto-generated?catch?block
			e.printStackTrace（）;
		}?catch?（NumberFormatException?e）?{
			//?TODO?Auto-generated?catch?block
			e.printStackTrace（）;
		}?catch?（IOException?e）?{
			//?TODO?Auto-generated?catch?block
			e.printStackTrace（）;
		}
		
	}
/**
?*?該方法實現(xiàn)算法
?*?@param?a
?*?@param?small
?*?@param?big
?*?@return
?*/
	public?long?findbest（int?a[]int?smallint?big）{

		long?number1number2number3number4number5;
		if（big-small<4）//當區(qū)間內(nèi)坐標很少時直接得到最佳坐標
			return?least（asmallbig）;
		else{
			//計算區(qū)間五個端點的評價值
			number1?=length（asmall）;
			number2?=length（asmall?+?（big-small）/3*1）;
			number3?=length（asmall?+?（big-small）/3*2）;
			number4?=length（asmall?+?（big-small）/3*3）;
			number5?=length（abig）;
			//根據(jù)五個端點評價值的大小淘汰一些區(qū)間，得到一個較小的區(qū)間繼續(xù)調(diào)用算法
			if（number1<=number2）?return?findbest（asmallsmall?+?（big-small）/3*1）;
			else?if（number1>=number2&&number2<=number3）?return?findbest（a?small?small?+?（big-small）/3*2）;
			else?if（number2>=number3&&number3<=number4）?return?findbest（asmall?+?（big-small）/3*1small?+?（big-small）/3*3）;
			else?if（number3>=number4&&number4<=number5）?return?findbest（a?small?+?（big-small）/3*2?big）;
		????else?if（number4>=number5）?return?findbest（a?small?+?（big-small）/3*3big）;
		????else?{System.out.println（“數(shù)據(jù)異常！“）;?return?0;}
			
		}
		
	}
	/*
	?*?該方法為輔助方法，用來計算某個坐標值與其他坐標值距離之和
	?*/
	private?long?leng

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件?????????29??2011-03-29?21:21??input_assign01_00.dat

?????文件?????????21??2011-03-06?14:58??input_assign01_01.dat

?????文件?????????40??2011-03-06?14:58??input_assign01_02.dat

?????文件????????101??2011-03-06?14:58??input_assign01_03.dat

?????文件????????226??2011-03-06?14:58??input_assign01_04.dat

?????文件????????644??2011-03-06?14:58??input_assign01_05.dat

?????文件???????1282??2011-03-06?14:58??input_assign01_06.dat

?????文件???????5811??2011-03-06?14:58??input_assign01_07.dat

?????文件??????21798??2011-03-06?14:58??input_assign01_08.dat

?????文件??????93790??2011-03-06?14:58??input_assign01_09.dat

?????文件?????117779??2011-03-06?14:58??input_assign01_10.dat

?????文件?????????72??2011-03-07?16:00??output.txt

?????文件???????3763??2011-03-07?16:17??postoffice.class

?????文件???????4179??2011-03-07?16:17??postoffice.java

-----------?---------??----------?-----??----

???????????????249535????????????????????14