首页 > ACM题库 > HDU-杭电 > HDU 3039-A high-dimensional problem[解题报告]HOJ
2014
02-27

HDU 3039-A high-dimensional problem[解题报告]HOJ

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':' ');
            }
        }
    }
}