找出距离最小的点对

找出距离最小的点对

分析

依次把每个点作为起点,计算和其余点的距离,保留更小的距离

	double[][] arr = {
			{1,1},
			{1,0.5},
			{2,1},
			{3,4},
			{2.2,1},
			{1,7},
			{4,1.8},
			{1.1,9},
			{3,5},
			{5,6}
	};
	double minDis = Double.MAX_VALUE;
	int minI=0;
	int minJ=0;
	//依次把每个点作为起点
	for(int i=0;i<arr.length;i++) {
		//计算和其余点的距离
		for(int j=i+1;j<arr.length;j++) {
			double x1 =arr[i][0];
			double x2=arr[j][0];
			double y1 =arr[i][1];
			double y2=arr[j][1];
			double dis=Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));//勾股定理
			if(dis<minDis) {
				minDis=dis;
				minI=i;
				minJ=j;
			}
		}
	}
	System.out.println("最小距离的点为:("+arr[minI][0]+","+arr[minI][1]+")("+arr[minJ][0]+","+arr[minJ][1]+"距离为:"+minDis);

rr[minJ][0]+","+arr[minJ][1]+“距离为:”+minDis);




上一篇:最近点对算法


下一篇:A1072 Gas Station (30分)