The Chef is a bit tired of graphs. He has spent far too many days calculating shortest paths, finding bipartite matchings, minimum cuts, and optimizing over NP-hard problems. He needs a break. Unfortunately for him, the food services industry doesn’t take breaks. Once again, the Chef has to navigate through an undirected graph to keep his business going.

In this particular problem, the layout of edges in the graph doesn’t matter very much. All that really matters is the distances between pairs of nodes. Given this, you have a great idea that will help the Chef not worry about graphs at all during this latest task. Rather than presenting the graph to the Chef, you will present something else.

After some thought, you have settled on the following. You will present the nodes of the graph as distinct points in d-dimensional Euclidean space. Each node v will be represented by a d-tuple of numbers pv = (xv,1, …, xv,d). The distance between two points is the usual Euclidean distance in d-dimensional space. That is, the distance between two points pu and pv representing nodes u and v is the square root of (xu,1 – xv,1)2 + … + (xu,d – xv,d)2.

The quality of such an assignment of nodes into points in Euclidean space is measured as follows. Let a(u,v) be the length of the shortest path connecting node u to node v in the graph and let b(u,v) be the distance between points pu and pv in Euclidean space. Define K as the minimum value of b(u,v)/a(u,v) over all pairs of distinct nodes (u,v). Similarily, define L as the maximum value of b(u,v)/a(u,v) over all pairs of distinct nodes (u,v). The quality of the solution is then d*L/K.

The idea behind this measurement is as follows. We want the distances between nodes in Euclidean space to be close to their distances in the original graph. So, K measures the greatest “contraction” between nodes when they are mapped into the Euclidean space. In the same way, L measures the greatest “stretch” between nodes. We put quotes around “contraction” and “stretch” because it could be that K > 1 or L < 1. Then the ratio L/K measures, in some way, the worst case distortion when embedding the nodes in Euclidean space. Finally, lower-dimensional Euclidean spaces are simpler so the final score is scaled by d.

Input

The first line consists of a single integer T ≤ 30 indicating the number of test cases to follow. Each test case begins with an integer n between 2 and 300. Then n lines follow, each containing n integers. This will be such that the j’th integer on the i’th row describes the distance of the shortest path between nodes i and j in the original graph. For i = j, this distance will be 0 and for i ≠ j this distance will be at least 1 and at most 10,000. Furthermore, the distance between i and j is equal to the distance between j and i because the graph is undirected. Since these represent shortest path distances, we also have that the distance from i to j is at most the distance from i to k plus the distance from k to j for any three nodes i,j,k.

Output

For each test case you are to output n+1 lines. The first line contains a single integer d which must be between 1 and 20. Then n lines follow where the i’th such line contains d integers describing the coordinates of the i’th point in Euclidean space. Each of these d integers must have absolute value at most 1,000,000. Also, each of these n points must be distinct.

To emphasize, any output that conforms to this output specification will be considered valid. The score for this output will be calculated as described above.

Scoring

Each test case will be given a score d*L/K where d is the dimension provided in the output and K and L will be calculated in the manner described in the problem statement. The score for all test cases in a test file is simply the sum of the scores of each test case.

Example

Input:
2
3
0 1 2
1 0 2
2 2 0
4
0 10 13 14
10 0 11 18
13 11 0 15
14 18 15 0

Output:
2
2 0
0 2
0 0
1
0
1
2
3

Explanation Of Sample Data

The provided answers are certainly not optimal for either test case, but they are valid solutions according to the output specification and such output would be accepted. The score for this output would be as follows.

In the first test case, we would have K = 1 since the Euclidean distance from the point representing node 2 to the points representing either 0 or 1 is exactly 2 and the Euclidean distance between the points representing nodes 0 and 1 exceeds 1. We also have L = sqrt(8)/1 since sqrt(8) is the distance between the points representing nodes 0 and 1 and 1 is distance between nodes 0 and 1 in the original graph. Thus, the score for this case is d*L/K = 2*sqrt(8) = 5.6568542.

In the second test case, the least ratio of Euclidean distance to original graph distance is between nodes 2 and 3. Their Euclidean distance is 1 and their original graph distance is 15 so K = 1/15. So, after scaling all Euclidean distance values by K, the worst graph distance to Euclidean distance ratio is between nodes 0 and 3. Their original graph distance was 14 and their Euclidean distance is only 3, so the value L is 3/14. Since d = 1, then the score for this test case is simply d*K/L = 1*3/14*15 = 3.2142857.

Test Data

There are roughly three types of test data. Some are hand-crafted to cause certain heuristics to perform poorly. Some are randomly generated from a variety of distributions. Some are known “worst-case” examples of graphs which cannot be represented very well in Euclidean space.

 

Solution:

#ifdef _MSC_VER

#define LOCAL
#define HACK

#endif

#include <cstdio>
#include <cstdlib>
#include <string>
#include <ctime>
#include <queue>
#include <algorithm>
#include <string.h>
#include <set>
#include <cmath>
#include <vector>

using namespace std;

/******************************/
#ifdef LOCAL
#include <cassert>
#define ASSERT(x) {if (!(x)) { printf(“DAI23.NB %dn”,__LINE__); exit(0); } }
#else
#ifdef HACK
#define ASSERT(x) while (!(x)) printf(“ZIG.WEIDAn”);
#else
#define ASSERT(x) ;
#endif
#endif
/******************************/

/******************************/
int read_int();

int __bufsize=0,__currentpos=0;
char __buf[32*1024];
char __next_char()
{
if (__currentpos==__bufsize)
{
__bufsize=fread(__buf,sizeof(char),32*1024,stdin);
if (__bufsize==0) return 0;
__currentpos=0;
}
return __buf[__currentpos++];
}
int read_int()
{
char c;
do{ c=__next_char(); } while (c<‘0′ || c>’9′);
int n=0;
for (;c>=’0′ && c<=’9′;c=__next_char()) n=n*10+(c-‘0′);
return n;
}
/******************************/

inline double sqr(double x)
{
return x*x;
}
int myrandom()
{
return ((rand()&32767)<<15)+(rand()&32767);
}
int random(int n)
{
return myrandom()%n;
}
int random(int s,int t)
{
return myrandom()%(t-s+1)+s;
}

typedef vector<int> VI;
const double pi=acos(-1.0);
#define MP(A,B) make_pair(A,B)
#define SIZE(A) ((int)A.size())
inline void checkmin(int &a,int b) { if (b<a) a=b; }
inline void checkmax(int &a,int b) { if (b>a) a=b; }
inline void checkmin(double &a,double b) { if (b<a) a=b; }
inline void checkmax(double &a,double b) { if (b>a) a=b; }

const int MAXDIMENSION=20;
const int MAXN=300;
const double TIMELIMIT_OVERALL=7.0;
const int MAXCOORDINATE=+1000000;
const int MINCOORDINATE=-1000000;

int convex_point_list[MAXDIMENSION][MAXN][MAXDIMENSION];

void build_convex_point_list_DFS(int *a,int depth,int sum,int dimension,int &cnt)
{
if (cnt>=MAXN) return;
if (depth==dimension)
{
if (sum!=0) return;
for (int i=0;i<dimension;i++) convex_point_list[dimension-1][cnt][i]=a[i];
cnt++;
return;
}
int max_a=(int)sqrt((double)sum)+1e-7;
for (a[depth]=-max_a;a[depth]<=max_a;a[depth]++)
build_convex_point_list_DFS(a,depth+1,sum-a[depth]*a[depth],dimension,cnt);
}
void build_convex_point_list()
{
int a[MAXDIMENSION];
for (int i=0;i<MAXN;i++)
convex_point_list[0][i][0]=i-MAXN/2;
for (int d=2;d<=MAXDIMENSION;d++)
for (int cnt=0,s=0;cnt<MAXN;s++)
build_convex_point_list_DFS(a,0,s,d,cnt);
}

class L2Graph
{
public:
int n;
int **a;
int **b,**c,**d;
double **sqra;

double best_score;
int best_dimension;
int **best_results;

int maxa;

void readin()
{
n=read_int();
#ifdef HACK
ASSERT(n>=2 && n<=300);
#endif
a=new int* [n];
for (int i=0;i<n;i++) a[i]=new int[n];
for (int i=0;i<n;i++) for (int j=0;j<n;j++) a[i][j]=read_int();
#ifdef HACK
for (int i=0;i<n;i++) ASSERT(a[i][i]==0);
for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (i!=j) ASSERT(a[i][j]==a[j][i] && a[i][j]>=1 && a[i][j]<=10000);
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) for (int k=0;k<n;k++) ASSERT(a[i][k]+a[k][j]>=a[i][j]);
#endif
}

void init_results()
{
best_score=1e100;
best_dimension=0;
best_results=new int* [n];
for (int i=0;i<n;i++) best_results[i]=new int[MAXDIMENSION];
}

void write_results()
{
printf(“%dn”,best_dimension);
for (int i=0;i<n;i++)
{
for (int j=0;j<best_dimension;j++) printf(“%d “,best_results[i][j]);
printf(“n”);
}
}

void prepare()
{
maxa=0;
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) if (a[i][j]>maxa) maxa=a[i][j];
b=new int* [n];
c=new int* [n];
d=new int* [n];
sqra=new double* [n];
int *q=new int[n];
for (int i=0;i<n;i++)
{
sqra[i]=new double[n];
for (int j=0;j<n;j++) sqra[i][j]=sqr(a[i][j]);
b[i]=new int[n];
c[i]=new int[n];
d[i]=new int[n];
for (int j=0;j<n;j++) q[j]=(a[i][j]<<9)+j;
sort(q,q+n);
for (int j=0;j<n;j++) b[i][j]=q[j]>>9,c[i][j]=q[j]&511;
for (int j=0;j<n;j++) d[i][c[i][j]]=(j==0 || b[i][j]!=b[i][j-1])?j:d[i][c[i][j-1]];
#ifdef HACK
for (int j=0;j<n;j++) ASSERT(a[i][j]==a[i][c[i][d[i][j]]]);
for (int j=0;j<n;j++) ASSERT(b[i][j]==a[i][c[i][j]]);
for (int j=0;j+1<n;j++) ASSERT(b[i][j]<=b[i][j+1]);
multiset<int> _s1,_s2;
for (int j=0;j<n;j++) _s1.insert(a[i][j]);
for (int j=0;j<n;j++) _s2.insert(b[i][j]);
ASSERT(_s1==_s2);
#endif
}
delete[] q;
}
L2Graph()
{
readin();
init_results();
prepare();
}

~L2Graph()
{
for (int i=0;i<n;i++) delete[] a[i];
delete[] a;
for (int i=0;i<n;i++) delete[] b[i];
delete[] b;
for (int i=0;i<n;i++) delete[] c[i];
delete[] c;
for (int i=0;i<n;i++) delete[] d[i];
delete[] d;
for (int i=0;i<n;i++) delete[] sqra[i];
delete[] sqra;
for (int i=0;i<n;i++) delete[] best_results[i];
delete[] best_results;
}

double get_score(int dimension,int **results)
{
double L=-1e100,K=1e100;
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++)
{
double d=0;
for (int k=0;k<dimension;k++) d+=sqr(results[i][k]-results[j][k]);
d/=sqra[i][j];
checkmax(L,d);
checkmin(K,d);
}
if (K<1e-12) return 1e200;
return dimension*sqrt(L/K);
}

void update_results_simple(int dimension,int **results,double score)
{
if (score<best_score)
{
best_score=score;
best_dimension=dimension;
for (int i=0;i<n;i++) for (int j=0;j<best_dimension;j++) best_results[i][j]=results[i][j];
}
}

void update_results_simple(int dimension,int **results)
{
update_results_simple(dimension,results,get_score(dimension,results));
}

void box_packing(int dimension)
{
int **results=new int*[n];
for (int i=0;i<n;i++) results[i]=new int[dimension];
for (int i=0;i<n;i++) for (int j=0;j<dimension;j++)
results[i][j]=convex_point_list[dimension-1][i][j];
update_results_simple(dimension,results);
for (int i=0;i<n;i++) delete[] results[i];
delete[] results;
}

void embed(const int MAXDIMENSION)
{
int cardinal=0;
for (int p=0;p<n;p+=(n-p+1)/2) cardinal++;
cardinal*=10;
#ifdef _MSC_VER
printf(“N = %d    CD = %dn”,n,cardinal);
#endif
int **results=new int* [n];
for (int i=0;i<n;i++) results[i]=new int[cardinal];
double **dst=new double* [n];
for (int i=0;i<n;i++) dst[i]=new double[n];
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) dst[i][j]=0;
int *permutation=new int[n];
for (int i=0;i<n;i++) permutation[i]=i;
int dimension=0;
for (int step=0;step<10;step++)
{
for (int i=0;i<n;i++) swap(permutation[i],permutation[random(i+1)]);
for (int p=0;p<n;)
{
int w=(n-p+1)/2;
checkmax(w,1);
checkmin(w,n-p);
for (int i=0;i<n;i++)
{
int d=1000000000;
for (int j=p;j<p+w;j++) checkmin(d,a[i][permutation[j]]);
results[i][dimension]=d;
}
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) dst[i][j]+=sqr(results[i][dimension]-results[j][dimension]);
dimension++;
p+=w;
}
#ifdef LOCAL
double min_rate=1e100,max_rate=-1e100;
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++)
{
double rate=dst[i][j]/sqra[i][j];
checkmin(min_rate,rate);
checkmax(max_rate,rate);
}
max_rate=sqrt(max_rate);
min_rate=sqrt(min_rate);
if (step+1==10)
{
printf(“step = %d   ratio = %.3lfn”,step,max_rate/min_rate);
printf(“step = %d   dimension = %d    min_rate = %.3lf    max_rate = %.3lfn”,step,dimension,min_rate,max_rate);
}
#endif
}
for (int d=dimension;d>0;d–)
{
const int res_cases=40;
int pa[res_cases],pb[res_cases];
double prate[res_cases];
for (int i=0;i<res_cases;i++) prate[i]=(i&1)?-1e100:1e100,pa[i]=pb[i]=-1;
int p_minrate=0,p_maxrate=1;
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++)
{
double rate=dst[i][j]/sqra[i][j];
if (rate>prate[p_maxrate])
{
prate[p_maxrate]=rate;
pa[p_maxrate]=i;
pb[p_maxrate]=j;
p_maxrate=1;
for (int k=1;k<res_cases;k+=2) if (prate[k]<prate[p_maxrate]) p_maxrate=k;
}
if (rate<prate[p_minrate])
{
prate[p_minrate]=rate;
pa[p_minrate]=i;
pb[p_minrate]=j;
p_minrate=0;
for (int k=0;k<res_cases;k+=2) if (prate[k]>prate[p_minrate]) p_minrate=k;
}
}
double local_min_rate=1e100,local_max_rate=-1e100;
for (int k=1;k<res_cases;k+=2) checkmax(local_max_rate,prate[k]);
for (int k=0;k<res_cases;k+=2) checkmin(local_min_rate,prate[k]);
if (local_min_rate<1e-11) break;
if (d<=MAXDIMENSION) update_results_simple(d,results,d*sqrt(local_max_rate/local_min_rate));
double *min_rates=new double[d];
double *max_rates=new double[d];
for (int i=0;i<d;i++) min_rates[i]=1e100,max_rates[i]=-1e100;
for (int i=0;i<res_cases;i++) if (pa[i]>=0)
{
int v1=pa[i],v2=pb[i];
for (int k=0;k<d;k++)
{
double rate=(dst[v1][v2]-sqr(results[v1][k]-results[v2][k]))/sqra[v1][v2];
checkmin(min_rates[k],rate);
checkmax(max_rates[k],rate);
}
}
int key=-1;
double best_ratio=1e100;
for (int i=0;i<d;i++) if (min_rates[i]>1e-10)
{
double ratio=max_rates[i]/min_rates[i];
if (ratio<best_ratio) best_ratio=ratio,key=i;
}
//printf(“EX  %d  %.3lfn”,d-1,sqrt(best_ratio));
delete[] min_rates;
delete[] max_rates;
if (key<0) break;
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) dst[i][j]-=sqr(results[i][key]-results[j][key]);
if (key!=d-1) for (int i=0;i<n;i++) swap(results[i][key],results[i][d-1]);
}
delete[] permutation;
for (int i=0;i<n;i++) delete[] dst[i];
delete[] dst;
for (int i=0;i<n;i++) delete[] results[i];
delete[] results;
}

void solve_as_conflict(int dimension,int **old_results,int ncomponents,int *component_size,int **component_vertices)
{
int max_value=0;
for (int i=0;i<n;i++) for (int j=0;j<dimension;j++) checkmax(max_value,old_results[i][j]);
int scale=(MAXCOORDINATE-MINCOORDINATE+1)/(max_value+7);
int **results=new int*[n];
for (int i=0;i<n;i++) results[i]=new int[dimension];
for (int i=0;i<n;i++) for (int j=0;j<dimension;j++) results[i][j]=(old_results[i][j]+3)*scale+MINCOORDINATE;
double min_rate=1e100,max_rate=-1e100;
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++)
{
double d=0;
for (int k=0;k<dimension;k++) d+=sqr(results[i][k]-results[j][k]);
if (d<0.5) continue;
d/=sqra[i][j];
checkmin(min_rate,d);
checkmax(max_rate,d);
}
if (min_rate>1e99) return;
double *min_r_local=new double[ncomponents];
double *max_r_local=new double[ncomponents];
for (int k=0;k<ncomponents;k++)
{
int size=component_size[k],pd=1;
if (size<=1) continue;
for (;pow((double)pd,dimension)<size-0.5;pd++);
for (int i=0;i<size;i++) for (int p=component_vertices[k][i],idx=i,j=0;j<dimension;j++,idx/=pd) results[p][j]=idx%pd;
double min_r=1e100,max_r=-1e100;
for (int i=0;i<size;i++) for (int j=i+1;j<size;j++)
{
int v1=component_vertices[k][i];
int v2=component_vertices[k][j];
double d=0;
for (int l=0;l<dimension;l++) d+=sqr(results[v1][l]-results[v2][l]);
d/=sqra[v1][v2];
checkmin(min_r,d);
checkmax(max_r,d);
}
min_r_local[k]=min_r;
max_r_local[k]=max_r;
}
for (int strategy=0;strategy<2;strategy++)
{
for (int k=0;k<ncomponents;k++)
{
int size=component_size[k],pd=1;
if (size<=1) continue;
for (;pow((double)pd,dimension)<size-0.5;pd++);
double min_r=min_r_local[k];
double max_r=max_r_local[k];
int delta=(strategy==0)?((int)sqrt(min_rate/min_r)+1):max((int)sqrt(max_rate/max_r),1);
checkmin(delta,scale/pd*4);
for (int i=0;i<size;i++) for (int p=component_vertices[k][i],idx=i,j=0;j<dimension;j++,idx/=pd)
results[p][j]=(old_results[p][j]+3)*scale+delta*(idx%pd)+MINCOORDINATE;
}
#ifdef HACK
for (int i=0;i<n;i++) for (int j=0;j<dimension;j++) ASSERT(results[i][j]>=MINCOORDINATE && results[i][j]<=MAXCOORDINATE);
#endif
update_results_simple(dimension,results);
}
delete[] min_r_local;
delete[] max_r_local;
for (int i=0;i<n;i++) delete[] results[i];
delete[] results;
}

void greedy(const int MAXDIMENSION)
{
int max_dimension=min(n,MAXDIMENSION);
int **results=new int* [n];
for (int i=0;i<n;i++) results[i]=new int[max_dimension];

int *component_size=new int[n];
int **component_vertices=new int* [n];
for (int i=0;i<n;i++) component_vertices[i]=new int[n];
int ncomponents=1;
component_size[0]=n;
for (int i=0;i<n;i++) component_vertices[0][i]=i;

bool *used=new bool[n];
for (int i=0;i<n;i++) used[i]=false;

int *idx=new int[n];
int *dup=new int[n];
int *prf=new int[n];
int counter=0;
for (int i=0;i<n;i++) idx[i]=0;

int step=0;
double **dst=new double* [n];
for (int i=0;i<n;i++) dst[i]=new double[n];
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) dst[i][j]=0;
for (;step<max_dimension;step++)
{
int min_esum=1000000000;
double min_evaluation=0;
int best_k=-1;
for (int k=0;k<n;k++) if (!used[k])
{
int esum=0;
for (int i=0;i<ncomponents;i++)
{
counter++;
int *pv=component_vertices[i],size=component_size[i];
for (int j=0;j<size;j++)
{
int key=d[k][pv[j]];
if (idx[key]!=counter)
dup[key]=1,idx[key]=counter;
else
dup[key]++,esum+=dup[key];
}
}
#ifdef HACK
int _exp_esum=0;
bool _visited[MAXN];
memset(_visited,false,sizeof(_visited));
for (int i=0;i<n;i++) if (!_visited[i])
{
int c=1;
for (int j=i+1;j<n;j++) if (dst[i][j]<0.5 && a[k][i]==a[k][j]) { c++; _visited[j]=true; }
_exp_esum+=c*(c+1)/2-1;
}
ASSERT(_exp_esum==esum);
#endif
double evaluation=0;
if (esum==0)
{
evaluation=1e100;
for (int i=0;i+1<n;i++)
{
int v1=c[k][i],v2=c[k][i+1];
if (v1>v2) swap(v1,v2);
checkmin(evaluation,(dst[v1][v2]+sqr(a[k][v1]-a[k][v2]))/sqr(a[v1][v2]));
}
}
if (esum<min_esum || esum==min_esum && evaluation>min_evaluation)
{
min_esum=esum;
min_evaluation=evaluation;
best_k=k;
}
}
used[best_k]=true;
int *acost=a[best_k];
for (int i=0;i<n;i++) results[i][step]=acost[i];
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) dst[i][j]+=sqr(acost[i]-acost[j]);
if (min_esum==0) break;
for (int i=ncomponents-1;i>=0;i–)
{
counter++;
int *pv=component_vertices[i],size=component_size[i];
for (int j=0;j<size;j++)
{
int key=d[best_k][pv[j]];
if (idx[key]!=counter)
dup[key]=1,idx[key]=counter;
else if ((++dup[key])==2)
component_size[ncomponents]=0,prf[key]=ncomponents++;
}
for (int j=0;j<size;j++)
{
int key=d[best_k][pv[j]];
if (dup[key]>=2)
{
int pos=prf[key];
component_vertices[pos][component_size[pos]++]=pv[j];
}
}
component_size[i]=0;
}
int new_ncomponents=0;
for (int i=0;i<ncomponents;i++)
if (component_size[i]>=2)
{
if (i!=new_ncomponents)
{
component_size[new_ncomponents]=component_size[i];
for (int j=0;j<component_size[i];j++) component_vertices[new_ncomponents][j]=component_vertices[i][j];
}
new_ncomponents++;
}
ncomponents=new_ncomponents;
#ifdef HACK
int _exp_esum2=0;
for (int i=0;i<ncomponents;i++)
{
int c=component_size[i];
_exp_esum2+=c*(c+1)/2-1;
}
ASSERT(_exp_esum2==min_esum);
#endif
solve_as_conflict(step+1,results,ncomponents,component_size,component_vertices);
}
if (step<max_dimension)
{
int start_step=(++step);
double *min_rate=new double[MAXDIMENSION];
double *max_rate=new double[MAXDIMENSION];
for (int i=0;i<max_dimension;i++) min_rate[i]=1e100,max_rate[i]=-1e100;
for (int step=start_step;step<max_dimension;step++)
{
const int res_cases=40;
int pa[res_cases],pb[res_cases];
double prate[res_cases];
for (int i=0;i<res_cases;i++) prate[i]=(i&1)?-1e100:1e100,pa[i]=pb[i]=-1;
int p_minrate=0,p_maxrate=1;
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++)
{
double rate=dst[i][j]/sqra[i][j];
if (rate>prate[p_maxrate])
{
prate[p_maxrate]=rate;
pa[p_maxrate]=i;
pb[p_maxrate]=j;
p_maxrate=1;
for (int k=1;k<res_cases;k+=2) if (prate[k]<prate[p_maxrate]) p_maxrate=k;
}
if (rate<prate[p_minrate])
{
prate[p_minrate]=rate;
pa[p_minrate]=i;
pb[p_minrate]=j;
p_minrate=0;
for (int k=0;k<res_cases;k+=2) if (prate[k]>prate[p_minrate]) p_minrate=k;
}
}
for (int k=0;k<res_cases;k+=2) checkmin(min_rate[step-1],prate[k]);
for (int k=1;k<res_cases;k+=2) checkmax(max_rate[step-1],prate[k]);
#ifdef HACK
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++)
{
double rate=dst[i][j]/sqra[i][j];
ASSERT(rate>=min_rate[step-1]-1e-11);
ASSERT(rate<=max_rate[step-1]+1e-11);
}
#endif
int best_k=-1;
double best_ratio=1e100;
for (int k=0;k<n;k++) if (!used[k])
{
double m1=1e100,m2=-1e100;
for (int i=0;i<res_cases;i++) if (pa[i]>=0)
{
int v1=pa[i],v2=pb[i];
double rate=(dst[v1][v2]+sqr(a[k][v1]-a[k][v2]))/sqra[v1][v2];
checkmin(m1,rate);
checkmax(m2,rate);
}
double ratio=m2/m1;
if (ratio<best_ratio) best_ratio=ratio,best_k=k;
}
used[best_k]=true;
for (int i=0;i<n;i++) results[i][step]=a[best_k][i];
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) dst[i][j]+=sqr(results[i][step]-results[j][step]);
}
for (int i=0;i<n;i++) for (int j=i+1;j<n;j++)
{
double rate=dst[i][j]/sqra[i][j];
checkmin(min_rate[max_dimension-1],rate);
checkmax(max_rate[max_dimension-1],rate);
}
int local_best_dimension=start_step;
double local_best_score=1e100;
for (int k=start_step;k<=max_dimension;k++) if (min_rate[k-1]>1e-15)
{
double score=k*sqrt(max_rate[k-1]/min_rate[k-1]);
if (score<local_best_score) local_best_score=score,local_best_dimension=k;
}
update_results_simple(local_best_dimension,results,local_best_score);
delete[] min_rate;
delete[] max_rate;
}
delete[] idx;
delete[] dup;
delete[] prf;
delete[] component_size;
for (int i=0;i<n;i++) delete[] component_vertices[i];
delete[] component_vertices;
delete[] used;
for (int i=0;i<n;i++) delete[] dst[i];
delete[] dst;
for (int i=0;i<n;i++) delete[] results[i];
delete[] results;
}

};

int main()
{
#ifdef _MSC_VER
freopen(“random.txt”,”r”,stdin);
//freopen(“random_sd.txt”,”r”,stdin);
//freopen(“sample.txt”,”r”,stdin);
//freopen(“sp1.txt”,”r”,stdin);
//freopen(“sp2.txt”,”r”,stdin);
#endif

double start_time=(double)clock();
double time_limit_overall=start_time+CLOCKS_PER_SEC*TIMELIMIT_OVERALL;

build_convex_point_list();
int testcase;
scanf(“%d”,&testcase);
#ifdef HACK
ASSERT(testcase<=30);
#endif
L2Graph **l2Graphs=new L2Graph* [testcase];
for (int case_id=0;case_id<testcase;case_id++)
l2Graphs[case_id]=new L2Graph();
for (int case_id=0;case_id<testcase;case_id++)
{
l2Graphs[case_id]->box_packing(2);
l2Graphs[case_id]->box_packing(3);
l2Graphs[case_id]->box_packing(4);
l2Graphs[case_id]->box_packing(5);
//l2Graphs[case_id]->greedy(10);
l2Graphs[case_id]->embed(20);
}
/*
vector<pair<double,int> > order;
for (int case_id=0;case_id<testcase;case_id++)
order.push_back(MP(l2Graphs[case_id]->best_score,case_id));
sort(order.begin(),order.end());
while ((double)clock()<time_limit_overall && !order.empty())
{
int case_id=order[SIZE(order)-1].second;
order.pop_back();
l2Graphs[case_id]->embed(20);
}
*/
#ifdef LOCAL
double __total_score=0;
for (int case_id=0;case_id<testcase;case_id++)
{
double s=l2Graphs[case_id]->best_score;
__total_score+=s;
printf(“CASE: %d    N: %d    SCORE: %.6lf       DIM : %dn”,case_id,l2Graphs[case_id]->n,s,l2Graphs[case_id]->best_dimension);
}
printf(“TOTAL_SCORE: %.6lfn”,__total_score);
printf(“Time Used = %.3lfn”,((double)clock()-start_time)/CLOCKS_PER_SEC);
#else
for (int case_id=0;case_id<testcase;case_id++)
l2Graphs[case_id]->write_results();
#endif

for (int case_id=0;case_id<testcase;case_id++)
delete l2Graphs[case_id];
delete[] l2Graphs;
return 0;
}