[2018.12.18]BZOJ1013 [JSOI2008]球形空间产生器sphere

秒速五厘米 2022-01-09 05:39 125阅读 0赞

设中心点坐标\\(B=(b\_1,b\_2,b\_3,...,b\_n)\\),球面上的点的坐标A=\\((a\_1,a\_2,a\_3,...,a\_n)\\)

则

\\(dist\_\{A,B\}=\\sqrt\{(a\_1-b\_1)^2+(a\_2-b\_2)^2+(a\_3-b\_3)^2+...+(a\_n-b\_n)^2\}\\)

\\((a\_1-b\_1)^2+(a\_2-b\_2)^2+(a\_3-b\_3)^2+...+(a\_n-b\_n)^2=dist\_\{A,B\}^2\\)

\\(a\_1^2-2a\_1b\_1+b\_1^2+a\_2^2-2a\_2b\_2+b\_2^2+a\_3^2-2a\_3b\_3+b\_3^2+...+a\_n^2-2a\_nb\_n+b\_n^2=dist\_\{A,B\}^2\\)

\\(-2a\_1b\_1-2a\_2b\_2-2a\_3b\_3-...-2a\_nb\_n=dist\_\{A,B\}^2-(a\_1^2+a\_2^2+a\_3^2+...+a\_n^2)-(b\_1^2+b\_2^2+b\_3^2+...+b\_n^2)\\)

设\\(dist\_\{A,B\}^2-(b\_1^2+b\_2^2+b\_3^2+...+b\_n^2)=k\\)

得\\(2a\_1b\_1+2a\_2b\_2+2a\_3b\_3+...+2a\_nb\_n+k=a\_1^2+a\_2^2+a\_3^2+...+a\_n^2\\)

由于\\(a\_1,a\_2,a\_3,...,a\_n\\)都是常数,所以这实际上是一个\\(n+1\\)元一次方程。

我们有\\(n+1\\)个这样的方程。

比如样例,可得以下方程:

\\(0b\_1+0b\_2+k=0\\)

\\(-2b\_1+2b\_2+k=2\\)

\\(2b\_1+0b\_2+k=1\\)

解得\\(b\_1=\\frac\{1\}\{2\},b\_2=\\frac\{3\}\{2\},k=0\\)

至于算法,[高斯消元][Link 1]求解即可。

code:

#include<bits/stdc++.h>
    using namespace std;
    struct equation{
        double n[15],x;
    }e[15];
    int n;
    double ans[15];
    void Printeq(){//debug
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)cout<<e[i].n[j]<<" ";
            cout<<"=>"<<e[i].x<<"\n";
        }
    }
    void Work(int x,int y){
        double v=-e[y].n[x]/e[x].n[x];
        for(int i=1;i<=n;i++)e[y].n[i]+=e[x].n[i]*v;
        e[y].x+=e[x].x*v;
    }
    void Solve(){
        for(int i=1;i<n;i++){
            for(int j=i;j<=n;j++){
                if(e[j].n[i]){
                    swap(e[j],e[i]);
                    break;
                }
            }
            for(int j=i+1;j<=n;j++)Work(i,j);
        }
        ans[n]=e[n].x/e[n].n[n];
        double k=0;
        for(int i=n-1;i>=1;i--,k=0){
            for(int j=i+1;j<=n;j++)k+=ans[j]*e[i].n[j];
            ans[i]=(e[i].x-k)/e[i].n[i];
        }
    }
    int main(){
        scanf("%d",&n);
        n++;
        for(int i=1;i<=n;i++){
            for(int j=1;j<n;j++)scanf("%lf",&e[i].n[j]),e[i].x+=e[i].n[j]*e[i].n[j],e[i].n[j]*=2;
            e[i].n[n]=1.0;
        }
        Solve();
        for(int i=1;i<n;i++)printf("%.3lf ",ans[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/xryjr233/p/BZOJ1013.html

[Link 1]: https://www.luogu.org/blog/xryjr233/post-20181218-gao-si-xiao-yuan-suan-fa-post