学步园

/*已知平面上若干个点的坐标。 

 需要求出在所有的组合中，4个点间平均距离的最小值（四舍五入，保留2位小数）。 

 比如有4个点：a,b,c,d, 则平均距离是指：ab, ac, ad, bc, bd, cd 这6个距离的平均值。 

 每个点的坐标表示为：横坐标,纵坐标 

 坐标的取值范围是：1~1000 

 所有点的坐标记录在in.txt中，请读入该文件，然后计算。 

 注意：我们测试您的程序的时候，in.txt 可能会很大，比如包含上万条记录。 

 举例： 
 如果，in.txt 内的值为： 

 10,10 
 20,20 
 80,50 
 10,20 
 20,10 

 则程序应该输出： 
 11.38 


 请编程，读入in.txt文件，计算并输出4个点平均距离的最小值。 


 要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。 
 相关的工程文件不要拷入。   
 不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。 
 */
import java.io.*;
import java.util.*;
import java.math.*;

class PP {
	public int x;
	public int y;

	public String toString() {
		return x + "," + y;
	}

	public PP(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

class RR {
	double x1;
	double x2;
	double y1;
	double y2;

	public RR() {

	}

	public RR(double x1, double y1, double x2, double y2) {
		this.x1 = x1;
		this.y1 = y1;
		this.x2 = x2;
		this.y2 = y2;
	}

	boolean isIn(PP p) {
		return (x1 < p.x && p.x < x2 && y1 < p.y && p.y < y2);
	}
}

public class PointDistance {
	public static double f(List<PP> lis, RR r) {
		if (lis.size() < 4)
			return 10000.0;
		if (lis.size() < 13) {
			double min = 10000;
			for (int i = 0; i < lis.size(); i++)
				for (int j = i + 1; j < lis.size(); j++)
					for (int k = j + 1; k < lis.size(); k++)
						for (int m = k + 1; m < lis.size(); m++) {
							double d = distance(lis.get(i), lis.get(j), lis
									.get(k), lis.get(m));
							if (d < min)
								min = d;
						}
			return min;
		}
		double x1a = r.x2;
		double x2a = r.x1;
		double y1a = r.y2;
		double y2a = r.y1;
		for (int i = 0; i < lis.size(); i++) {
			PP p = lis.get(i);
			if (p.x < x1a)
				x1a = p.x;
			if (p.x > x2a)
				x2a = p.x;
			if (p.y < y1a)
				y1a = p.y;
			if (p.x > y2a)
				y2a = p.y;
		}
		r.x1 = x1a;
		r.x2 = x2a;
		r.y1 = y1a;
		r.y2 = y2a;

		RR r1 = new RR();
		RR r2 = new RR();
		RR r3 = new RR();
		RR r4 = new RR();

		r1.x1 = r.x1;
		r1.y1 = r.y1;
		r1.x2 = r.x1 * 0.25 + r.x2 * 0.75;
		r1.y2 = r.y1 * 0.25 + r.y2 * 0.75;

		r2.x1 = r.x1 * 0.75 + r.x2 * 0.25;
		r2.y1 = r.y1 * 0.75 + r.y2 * 0.25;
		r2.x2 = r.x2;
		r2.y2 = r.y2;

		r3.x1 = r.x1;
		r3.y1 = r.y1 * 0.75 + r.y2 * 0.25;
		r3.x2 = r.x1 * 0.25 + r.x2 * 0.75;
		r3.y2 = r.y2;

		r4.x1 = r.x1 * 0.75 + r.x2 * 0.25;
		r4.y1 = r.y1;
		r4.x2 = r.x2;
		r4.y2 = r.y1 * 0.25 + r.y2 * 0.75;

		List<PP> t1 = new Vector<PP>();
		List<PP> t2 = new Vector<PP>();
		List<PP> t3 = new Vector<PP>();
		List<PP> t4 = new Vector<PP>();

		for (int i = 0; i < lis.size(); i++) {
			PP p = lis.get(i);
			if (r1.isIn(p))
				t1.add(p);
			if (r2.isIn(p))
				t2.add(p);
			if (r3.isIn(p))
				t3.add(p);
			if (r4.isIn(p))
				t4.add(p);
		}

		double d1 = f(t1, r1);
		double d2 = f(t2, r2);
		double d3 = f(t3, r3);
		double d4 = f(t4, r4);
		double d = d1;
		if (d2 < d)
			d = d2;
		if (d3 < d)
			d = d3;
		if (d4 < d)
			d = d4;

		return d;
	}

	public static double distance(PP a1, PP b1) {
		double dx = Math.abs(a1.x - b1.x);
		double dy = Math.abs(a1.y - b1.y);
		return Math.sqrt(dx * dx + dy * dy);
	}

	public static double distance(PP a, PP b, PP c, PP d) {
		double dis = (distance(a, b) + distance(a, c) + distance(a, d)
				+ distance(b, c) + distance(b, d) + distance(c, d)) / 6.0;
		return dis;
	}

	public static List<PP> readPoints(String fname) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(
				new FileInputStream(fname)));
		List<PP> lis = new Vector<PP>();
		for (;;) {
			String s = br.readLine();
			if (s == null)
				break;

			String[] ss = s.split(",");
			PP e = new PP(0, 0);
			e.x = Integer.parseInt(ss[0]);
			e.y = Integer.parseInt(ss[1]);
			lis.add(e);
		}
		br.close();
		return lis;

	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		List<PP> lis = readPoints("in.txt");
		double x = f(lis, new RR(0, 0, 1000, 1000));
		System.out.printf("%.2f",x);
	}
}