java实现杭电acm1到23题

import java.util.Arrays; import java.util.Scanner; /*第4章 分治法 寻找最近点对*/ //fail: Time Limit Exceeded public class QuoitDesign_1007 { /** * @param args */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int cases = sc.nextInt(); if (cases == 0) System.exit(0); Point[] Points = new Point[cases]; for (int i = 0; i < cases; i++) { Points[i] = new Point(); Points[i].x = sc.nextDouble(); Points[i].y = sc.nextDouble(); } Point.quickSort(Points, 0, cases - 1); // Arrays.sort(Points);// // 按照x坐标升序对点预排序,n*log(n)的复杂度---Arrays提供的静态排序方法 Point[] result = new Point[2]; result = getNearestPoints(Points); double d = dPoints(result[0], result[1]); System.out.println(String.format("%.2f", d)); } } public static Point[] getNearestPoints(Point[] Points) { // 从一个点数组里面找到最近的两个点，并返回这两个点 Point[] result = new Point[2]; if (Points.length == 3 || Points.length == 2) // 递归结束的条件 result = getNear(Points); else // 多于3个点，分治，分别找出两个子集合的最近点对，然后合并结果 { Point[] left = Arrays.copyOfRange(Points, 0, Points.length / 2);// 最后一个下标不包括 Point[] right = Arrays.copyOfRange(Points, Points.length / 2, Points.length); // 得到2个子集里面分别最短距离的2个点 Point[] result1 = getNearestPoints(left); Point[] result2 = getNearestPoints(right); double d1 = dPoints(result1[0], result1[1]); double d2 = dPoints(result2[0], result2[1]); // 忘了将result赋值 if (d1 <= d2) result = result1; else result = result2; // 合并结果：找到全局距离最短的两个点 double dmin = Math.min(d1, d2); int y1 = left.length - 1;// 两个x的分界点 int y2 = y1 + 1; // 在Points.length/2是一个整数时是错误的 // int x1 = Points[Points.length/2 - 1].x;//两个x的分界点 // int x2 = Points[Points.length/2].x; for (int i = y1; i >= 0; i--) { // if(x2 - Points[i].x > dmin) //直接导致调试很久都不知道错在哪！！！！！！ if (Points[y2].y - Points[i].y > dmin) break; else // for(int j = Points.length/2;j < Points.length;j++) for (int j = y2; j < Points.length; j++) { // System.out.println(Points[j].y); // if(Points[j].x - x1 > dmin) if (Points[j].y - Points[y1].y > dmin) break; else { double temp = dPoints(Points[i], Points[j]); // System.out.println(temp); if (temp < dmin) { dmin = temp; result[0] = Points[i]; result[1] = Points[j]; } } } } } return result; } private static Point[] getNear(Point[] Points) { // 返回仅有2个点或者三个点的点数组中距离最小的两个点 Point[] result = new Point[2]; if (Points.length == 2) result = Points; else // 有3个点,枚举求距离最短的两个点 { double d1 = dPoints(Points[0], Points[1]); double d2 = dPoints(Points[0], Points[2]); double d3 = dPoints(Points[1], Points[2]); if (d1 <= d2 && d1 <= d3) { result[0] = Points[0]; result[1] = Points[1]; } else if (d2 <= d3) { result[0] = Points[0]; result[1] = Points[2]; } else { result[0] = Points[1]; result[1] = Points[2]; } } return result; } private static double dPoints(Point a, Point b) { // 求两个点之间的距离 return Math.pow(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2), 0.5); } } class Point { // 二维的点 public double x; public double y; public Point() { } public Point(double x, double y) { this.x = x; this.y = y; } public static void quickSort(Point[] a, int lo0, int hi0) { int lo = lo0; // 相当于i，左 int hi = hi0; // 相当于j, 右 if (lo >= hi) // 判断是否到中间了 return; // 确定指针方向的逻辑变量，也就是从左搜索还是向右搜索 boolean transfer = true; while (lo != hi) { if (a[lo].y > a[hi].y) { // 交换数字 swap(a, lo, hi); // 决定下标移动，还是上标移动 transfer = (transfer == true) ? false : true; } // 将指针向前或者向后移动 if (transfer) hi--; else lo++; // 显示每一次指针移动的数组数字的变化 /* * for(int i = 0; i < a.length; ++i) { System.out.print(a[i] + ","); * } System.out.print(" (lo,hi) = " + "(" + lo + "," + hi + ")"); * System.out.println(""); */ } // 将数组分开两半，确定每个数字的正确位置 lo--; hi++; quickSort(a, lo0, lo); quickSort(a, hi, hi0); } // 两个元素换位的方法 private static void swap(Point[] arr, int a, int b) { Point temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }