2015
04-14

# Clear All of Them II

Acmers have been the Earth Protector against the evil enemy for a long long time, now it’s your second turn to protect our home.
There are 4 * n enemies in the map. Your task is to clear all of them with your super laser gun at the fixed position (x, y).
For each laser shot, your laser beam can reflect 3 times (must be 3 times), which means it can kill 4 enemies at one time. And the energy this shot costs is the total length
of the laser path.
For example, if you are at (0, 0), and use one laser shot kills the 4 enemies in the order of (3, 4), (6, 0), (3, 0), (0, 4), then the energy this shot costs is 5.0 + 5.0 + 3.0 + 5.0
= 18. 00.
To save the energy, you decide to use the Greedy Algorithm, which means for each shot, you select four existed enemies and decide the reflect order, so that this shot’s
energy cost is minimum. If there is a tie, we assure that choosing the shot whose four enemies’ average distance to you is smallest can avoid a tie. (See the sample for
more details)
Now, telling you your position and the 4n enemies’ position, can you tell me how much energy you need in total to clear all of them?
Note that:
> Each enemy can only be attacked once.
> All the positions will be unique.
> You must attack 4 different enemies in one shot.
> You can’t change your position.

The first line contains a single positive integer T( T <= 20 ), indicates the number of test cases.
For each case:
There are 2 integers x and y in the first line, which means your position.
The second line is an integer n(1 <= n <= 50), denote there are 4n enemies.
Then there following 4n lines, each line have 2 integers denote the position of an enemy.
All the position integers are between -1000 and 1000.

The first line contains a single positive integer T( T <= 20 ), indicates the number of test cases.
For each case:
There are 2 integers x and y in the first line, which means your position.
The second line is an integer n(1 <= n <= 50), denote there are 4n enemies.
Then there following 4n lines, each line have 2 integers denote the position of an enemy.
All the position integers are between -1000 and 1000.

2

0 0
1
6 0
3 0
3 4
0 4

0 0
2
1 0
2 0
3 0
4 0
1 1
1 2
1 3
1 4

Case #1: 14.00
Case #2: 13.00

HintCase #2:
For the first shot,
(0, 0)->(1, 0)->(2, 0)->(3, 0)->(4, 0) cost 4 energy;
and (0, 0)->(1, 0)->(1, 1)->(1, 2)->(1, 3) cost 4 energy, too.
But (0, 0)->(1, 0)->(1, 1)->(1, 2)->(1, 3)’s average distance to you(0, 0) is smallest(which is about 1.9531398), so we choose (0, 0)->(1, 0)->(1, 1)->(1, 2)->(1, 3)
for the first shot. 

4*n个点，每次选4个点，使得距离（射击点—1—2—3—4）最短。问最终将所有点都选完的最小距离

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define EPS 1e-4
const int MAXN = 201;
int n;
double ans,mi;
struct Point{
double x,y;
void input(){
scanf("%lf%lf",&x,&y);
}

}ps[MAXN],o;
inline double pdis(Point a,Point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int flag[MAXN];
int minodis[MAXN][MAXN];
int mindis[MAXN][MAXN];
double odis[MAXN];
double ppdis[MAXN][MAXN];
int si,ssi,o1,o2,o3,o4;
inline int cmp1(int a,int b){
return ppdis[a][si] + EPS < ppdis[b][si];
}
inline int cmp2(int a,int b){
return ppdis[a][ssi] + odis[a] + EPS < ppdis[b][ssi] + odis[b];
}

inline void update(int p1,int p2,int p3,int p4){

double tmp = odis[p1] + ppdis[p1][p2] + ppdis[p2][p3] + ppdis[p3][p4];
if(tmp+EPS < mi){
mi = tmp;
o1 = p1;o2 = p2;o3 = p3;o4 = p4;
}
else if(fabs(tmp-mi) < EPS){
if(odis[p1]+odis[p2]+odis[p3]+odis[p4] < odis[o1]+odis[o2]+odis[o3]+odis[o4]){
o1 = p1;o2 = p2;o3 = p3;o4 = p4;
}
}
}
int main(){
int cas;
scanf("%d",&cas);
for(int kcas = 1; kcas <= cas; ++kcas){
o.input();
scanf("%d",&n);
n = 4*n;
for(int i = 0; i < n; ++i)ps[i].input();
for(int i = 0; i < n; ++i){
odis[i] = pdis(o,ps[i]);
for(int j = 0; j < n; ++j){
ppdis[i][j] = pdis(ps[i],ps[j]);
}
}
for(int i = 0; i < n; ++i){
int cnt = 0;
for(int j = 0; j < n; ++j){
if(i == j)continue;
mindis[i][cnt] = j;
minodis[i][cnt++] = j;
}
si = i;ssi = i;
sort(mindis[i],mindis[i]+cnt,cmp1);
sort(minodis[i],minodis[i]+cnt,cmp2);
}
ans = 0.0;
memset(flag,0,sizeof(flag));
int tmpn = n/4;
while(tmpn --){
mi = 1e100;
for(int i = 0; i < n; ++i){
if(flag[i])continue;
for(int j = 0; j < n; ++j){
if(i == j)continue;
if(flag[j])continue;
int t = 0;
while ((minodis[i][t] == i || minodis[i][t] == j ||flag[minodis[i][t]]))t++;
int tmp1 = minodis[i][t];
t++;
while (minodis[i][t] == i || minodis[i][t] == j ||flag[minodis[i][t]])t++;
int tmp12 = minodis[i][t];

t = 0;
while ((mindis[j][t] == i || mindis[j][t] == j || flag[mindis[j][t]]))t++;
int tmp2 = mindis[j][t];
t++;
while (mindis[j][t] == i || mindis[j][t] == j || flag[mindis[j][t]])t++;
int tmp22 = mindis[j][t];
double tmp;
if(tmp1 == tmp2){
update(tmp12,i,j,tmp2);
update(tmp1,i,j,tmp22);
continue;
}

update(tmp1,i,j,tmp2);
}
}
ans += mi;
flag[o1] = flag[o2] = flag[o3] = flag[o4] = 1;
//	printf("%d %d %d %d\n",o1,o2,o3,o4);
}
printf("Case #%d: ",kcas);
printf("%.2lf\n",ans);
}
return 0;
}