The sky is beautiful, there are many stars in it. Xiaoming is curious, he came out with a strange idea. He want to divide the stars into two groups A,B and calculate the sum of the distance of any two stars in different groups. And he wants to make the sum
maximal as possible. Given the coordinate of n stars in the Sky, you are to write a program to calculate the maximal sum.
Input
The input cotains multi test cases. The first line is a nubmer n, the number of stars (n <= 30) next n lines each contains three float numbers the coordinate of the stars.
Output
maximal sum, 3 digit after point
Sample Input
5 0 0 0 0 10 0 10 0 0 10 10 0 5 5 5
Sample Output
65.605
//
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct Point
{
double x,y,z;
};
Point a[40];
int n;
double total,_min;
double d[40][40];
double dis1[40][1<<8];//节点i到0-7点j状态的距离和
double dis2[40][1<<8];//节点i到8-15点j状态的距离和
double dis3[40][1<<8];//节点i到16-23点j状态的距离和
double dis4[40][1<<8];//节点i到24-31点j状态的距离和
double dist(Point h,Point k)
{
double d1=h.x-k.x,d2=h.y-k.y,d3=h.z-k.z;
return sqrt(d1*d1+d2*d2+d3*d3);
}
//求最小值容易剪枝
void dfs(int u,int state,double nds)
{
if(nds>=_min) return ;//剪枝
if(u==n)
{
_min=min(_min,nds);
return ;
}
//假设第一个点是A集合,小剪枝
if(u==0)
{
dfs(u+1,state,nds);
return ;
}
int rm=(1<<8)-1;
//A 0
int stateA=(~state)&((1<<u)-1);//前u-1个在A集合中的元素
dfs(u+1,state,nds+
dis1[u][(stateA&rm)]+//最后8位
dis2[u][(stateA>>8)&rm]+//最后16-9位
dis3[u][(stateA>>16)&rm]+//最后24-17位
dis4[u][(stateA>>24)&rm]);//最后32-25位
//B 1
int stateB=state&((1<<u)-1);//前u-1个在B集合中的元素
dfs(u+1,state|(1<<u),nds+
dis1[u][(stateB&rm)]+//最后8位
dis2[u][(stateB>>8)&rm]+//最后16-9位
dis3[u][(stateB>>16)&rm]+//最后24-17位
dis4[u][(stateB>>24)&rm]);//最后32-25位
}
int main()
{
while(scanf("%d",&n)==1)
{
for(int i=0;i<n;i++) scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z);
memset(d,0,sizeof(d));
total=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
d[i][j]=d[j][i]=dist(a[i],a[j]);
total+=d[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int state=0;state<(1<<8);state++)
{
dis1[i][state]=dis2[i][state]=dis3[i][state]=dis4[i][state]=0;
for(int j=0;j<8;j++)
{
if(state&(1<<j))
{
dis1[i][state]+=d[i][j];
dis2[i][state]+=d[i][j+8];
dis3[i][state]+=d[i][j+16];
dis4[i][state]+=d[i][j+24];
}
}
}
}
_min=1e25;
dfs(0,0,0);
printf("%.3lf\n",total-_min);
}
return 0;
}