2015
09-17

# Plane Partition

A plane partition is a two-dimensional array of nonnegative integers ai,j (0<=i<n, 0<=j<m) that satisfies
1. 0<=ai,j<=p
2. ai,j>=ai,j+1
3. ai,j>=ai+1,j

In this problem, we add some additional constrains in the following form:
Given x, y, z, there exists some integer k (may be negative) such that ax+k,y+k=z+k.

Note: For i and j do not satisfy 0<=i<n and 0<=j<m, ai,j does not exist.

Count how many valid plane partitions are there.

First line, number of test cases, T.
Following are T test cases. For each test case, the first line contains four integers, n, m, p, t, where the last one is the number of additional constraints.
Following are t lines, each line contains three integers, x, y, z.

T<=200
1<=n,m,p<=7
0<=x,y,z<=7
It’s possible that there is no valid plane partitions.

First line, number of test cases, T.
Following are T test cases. For each test case, the first line contains four integers, n, m, p, t, where the last one is the number of additional constraints.
Following are t lines, each line contains three integers, x, y, z.

T<=200
1<=n,m,p<=7
0<=x,y,z<=7
It’s possible that there is no valid plane partitions.

2
1 1 1 0
1 1 1 1
1 1 1

2
1

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 60;
int n, p, q, x[N], y[N];
double dist[N][N];
double cal(double dx,double dy){
return sqrt(dx*dx + dy*dy);
}
bool done[N];
double d[N];
double solve(){
memset(done,0,sizeof(done));
double res = dist[p][q];
done[p]=done[q]=1;
for(int i=1; i<=n; i++){
d[i] = min(dist[p][i], dist[q][i]);
}
for(int i=3; i<=n; i++){
int j=-1;
for(int k=1; k<=n; k++){
if(done[k]) continue;
if(j==-1 || d[k]<d[j])  j=k;
}
done[j]=1;
res += d[j];
for(int k=1; k<=n; k++){
if(!done[k])    d[k] = min(d[k], dist[j][k]);
}
}
return res;
}
int main(){
while(~scanf("%d", &n) && n){
scanf("%d %d", &p, &q);
for(int i=1; i<=n; i++){
scanf("%d %d", x+i, y+i);
for(int j=1; j<i; j++){
dist[i][j] = dist[j][i] = cal(x[i]-x[j], y[i]-y[j]);
}
dist[i][i]=0.0;
}
printf("%.2lf\n", solve());
}
return 0;
}