2014
02-27

# A high-dimensional problem

As we all know, a point in n-dimensional space can be represented as a vector (x1, x2, …, xn), where xi is a real number. Given a vector D = (d1, d2, …, dn), we can generate a series of planes perpendicular to D: each plane satisfies the condition that for any two point on the plane, say A = (a1, a2, …, an), B = (b1, b2, …, bn), the inner product of (A – B) and D is zero, ie. (a1 – b1) * d1 + (a2 – b2) * d2 + … + (an – bn) * dn = 0, and we call D the normal vector of the plane. let A * B denotes the inner product of A and B.

Here are n planes in n-dimensional space: S1, S2, …, Sn with normal vector D1, D2, …, Dn respectively. And P1, P2, …, Pn lies on S1, S2,…, Sn respectively. We don’t know the coordinates of P1, P2, …, Pn, but instead we know D1 * P1, D2 * D2, …, Dn * Pn. Can we find out the point of intersection of S1, S2, …, Sn?

There will be multiple test cases. Each data set will be formatted according to the following description:
1. A line containing two integers n, m, 3 <= n <= 100, 1 <= m <= n, m represents the number of queries to the same D1, D2, …, Dn.
2. line 1 + i(1 <= i <= n) : n real number denoting the coordinates of Di.
3. line 1 + n + i(1 <= i <= m): n real number denoting D1 * P1, D2 * P2, …, Dn * Pn.

There will be multiple test cases. Each data set will be formatted according to the following description:
1. A line containing two integers n, m, 3 <= n <= 100, 1 <= m <= n, m represents the number of queries to the same D1, D2, …, Dn.
2. line 1 + i(1 <= i <= n) : n real number denoting the coordinates of Di.
3. line 1 + n + i(1 <= i <= m): n real number denoting D1 * P1, D2 * P2, …, Dn * Pn.

3 1
1 0 0
0 1 0
0 0 1
1 1 1

1.00 1.00 1.00

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
double a[105][205],b[105],ans;
int main()
{
int n,q,m;
while(scanf("%d%d",&n,&q)!=EOF)
{
m=2*n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%lf",&a[i][j]);
if(i==j)
a[i][n+j]=1;
else
a[i][n+j]=0;
}
for(int i=1;i<=n;i++)
{
int pos=i;
for(;pos<=n;pos++)
if(fabs(a[pos][i])>1e-6)break;
if(pos!=i)
for(int k=i;k<=m;k++)
swap(a[i][k],a[pos][k]);
double temp=a[i][i];
for(int j=i;j<=m;j++)a[i][j]/=temp;
for(int j=1;j<=n;j++)
{
if(j==i)continue;
temp=a[j][i];
for(int k=i;k<=m;k++)
a[j][k]-=a[i][k]*temp;
}
}
while(q--)
{
for(int i=1;i<=n;i++)
scanf("%lf",&b[i]);
for(int i=1;i<=n;i++)
{
ans=0;
for(int j=n+1;j<=m;j++)
ans+=a[i][j]*b[j-n];
printf("%.2f%c",ans,i==n?'\n':' ');
}
}
}
}