学步园

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

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

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

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

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

例如，如果程序输入：
10,10
20,20
80,50
10,20
20,10

则程序应该输出：
11.38

#include <iostream>  
#include <fstream>  
#include <vector>  
#include <cmath>  
#include <iomanip>  
#include <algorithm>  

using namespace std;  

struct Point  
{  
	int x,y;  
	int x2y2;  
	Point()  
	{  
		return;  
	}  
	Point(int t_x,int t_y)  
		:x(t_x),  
		y(t_y)  
	{  
		x2y2 = t_x * t_x + t_y * t_y;  
	}  
	const Point& operator=(const Point& point)  
	{  
		x = point.x;  
		y = point.y;  
		x2y2 = point.x2y2;  

		return *this;  
	}  
};  

bool operator<(const Point& left,const Point& right)  
{  
	if (left.x2y2 < right.x2y2)  
	{  
		return true;  
	}  
	return false;  
}  
bool operator==(const Point& left,const Point& right)  
{  
	if (left.x2y2 == right.x2y2)  
	{  
		return true;  
	}  
	return false;  
}  
typedef vector<Point> PointArray;  

static double min_sum = 0x3f3f3f3f;  
static int ps[4];  

inline int get_dis_no_sqrt(PointArray& points,int x,int y)  
{  
	int off_x = 0;  
	int off_y = 0;  

	off_x = points[x].x - points[y].x;  
	off_y = points[x].y - points[y].y;  

	off_x = off_x * off_x;  
	off_y = off_y * off_y;  
	return off_x + off_y;  
}  
inline void my_sort(PointArray& points)  
{  
	int s = points.size();  

	for (int i = 0;i < s;i++)  
	{  
		int min_x_y = 0x3f3f3f3f;  

		/*对所有的进行重排*/  
		for (int j = i + 1;j < s;j++)  
		{  
			if (points[j].x - points[i].x > min_x_y || points[j].y - points[i].y > min_x_y)  
			{  
				break;  
			}  
			int dis_i_i_1 = get_dis_no_sqrt(points,i,i + 1);  
			int dis_i_j = get_dis_no_sqrt(points,i,j);  

			if (dis_i_i_1 < dis_i_j)  
			{  
				continue;  
			}  
			/*向后移动*/  
			Point p = points[j];  
			for (int k = j;k > i + 1;k--)  
			{  
				points[k] = points[k - 1];  
			}  
			points[i + 1] = p;  
			min_x_y = (int)sqrt(dis_i_j * 1.0) + 1;  

		}  
	}  
	return;  
}  

inline double get_dis(PointArray& points,int x,int y)  
{  
	return sqrt(double(get_dis_no_sqrt(points,x,y)));  
}  
void search(PointArray& points,int p4[],int off,int lev)  
{  
	if (lev == 4)  
	{  
		double sum = 0;  

		for (int i = 0;i < 3;i++)  
		{  
			sum += get_dis(points,p4[i],p4[i + 1]);  
		}  
		sum += get_dis(points,p4[0],p4[2]);  
		sum += get_dis(points,p4[0],p4[3]);  
		sum += get_dis(points,p4[1],p4[3]);  
		if (min_sum > sum)  
		{  
			min_sum = sum;  
			for (int i = 0;i < 4;i++)  
			{  
				ps[i] = p4[i];  
			}  
		}  
		return;  
	}  
	for (int i = off;i < points.size();i++)  
	{  
		if (get_dis(points,i,p4[0]) > min_sum)  
		{  
			break;  
		}  
		p4[lev] = i;  
		search(points,p4,i + 1,lev + 1);  
	}  
	return;  
}  
int main()  
{  
	fstream fst("in.txt",ios::in);  
	int x,y;  
	char ch;  

	PointArray points;  

	while (fst >> x >> ch >> y)  
	{  
		Point p(x,y);  
		points.push_back(p);  
	}  

	sort(points.begin(),points.end());  
	my_sort(points);  
	int s = points.size();  
	if (s < 4)  
	{  
		cout << "0.00" << endl;  
	}  
	else  
	{  
		int p4[4] = {0};  

		for (int i = 0;i < s - 4;i++)  
		{  
			memset(p4,0,sizeof(p4));  
			p4[0] = i;  
			search(points,p4,i,0);  
		}  

		cout << fixed << setprecision(2) << min_sum / 6 << endl;  
		cout << endl;  
	}  
	return 0;  
}