hihocoder 1627

The 2017 ACM-ICPC Asia Beijing Regional Contest 北京区域赛 B、K-Dimensional Foil

题意

给定N个点的前3维左边，和他们的欧几里得距离，求至少多少维，才能满足这个距离。

题解

施密特正交化可证明如果有解则存在下三角矩阵的解。距离平方和先减去前3维的距离平方和，这样就相当于去掉了3维。然后依次考虑每个点，看当前维度能不能满足答案，不能则加一维，再根据距离确定新加一维的值。

代码

#include <bits/stdc++.h>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))

#define rep(i,l,r) for(int i=l,ed=r;i<ed;++i)

#define db(x) cout<< #x <<"="<<(x)<<endl

#define sqr(x) ((x)*(x))

typedef long long ll;

typedef long double dd;

const dd EPS=1e-10;

const int N=110;

int n,t;

dd a[N][N];//position of i_th point in j_th dimension

dd d[N][N];//remain distance between i_th and j_th point

int num[N];//k_th dimension first appears on num[k]_th point

dd calc(int i,int j,int dim){//distance between j_th point and i_th point (dimension 0~dim)

	dd sum=0;

	rep(k,0,dim+1)

		sum+=sqr(a[j][k]-a[i][k]);

	return sum;

}

bool solve(){

	cin>>n;

	rep(i,0,n)

	rep(j,0,3)

		cin>>a[i][j];

	int flag=0;

	rep(i,0,n)

	rep(j,i+1,n){

		cin>>d[i][j];

		rep(k,0,3)d[i][j]-=sqr(a[i][k]-a[j][k]);

		if(d[i][j]<-EPS){

			flag=1;

		}

		d[j][i]=d[i][j];

	}

	if(flag)return 0;

	mem(a,0);

	mem(num,0);

	int k=0;

	rep(i,1,n){

		dd dis0=d[i][0];

		rep(j,0,k){

			if(a[num[j]][j]>EPS)

				a[i][j]=(calc(i,num[j],k)-calc(i,0,k)+d[i][0]-d[i][num[j]])/2./a[num[j]][j];

			dis0-=sqr(a[i][j]);

			if(dis0<-EPS)return 0;

		}

		if(dis0>EPS){

			a[num[k]=i][k]=sqrt(dis0);

			k++;

		}

		rep(j,0,i)

			if(fabs(calc(i,j,k)-d[i][j])>EPS)return 0;

	}

//	rep(i,0,n)

//	rep(j,0,k){

//		cout<<a[i][j]<<(" \n"[j==k-1]);

//	}

	cout<<k+3<<endl;

	return 1;

}

int main(){

	ios::sync_with_stdio(false);

	cin>>t;

	while(t--){

		if(!solve())cout<<"Goodbye World!"<<endl;

	}

	return 0;

}