【BZOJ 1013】球形空间产生器sphere（高斯消元）

球形空间产生器sphere HYSBZ - 1013 （高斯消元）

原题地址

题意

给出n维的球上的n个点，问原球体球心。

提示

n维球体上两点距离公式\(dist = \sqrt{ (a1-b1)^2 + (a2-b2)^2 + … + (an-bn)^2 }\)

解法

\((x1-x0)^2\) --1

\((x2-x0)^2\) --2

2-1得

\((x2-x0)^2-(x1-x0)^2=0\)

-->

\(2(x2-x1)x0=(x2-x1)^2\)

类似可得

\(2(x2-x1)x0+2(y2-y1)y0+....=(x2-x1)^2+(y2-y1)^2....\)

n+1个点，可以得到n的方程，由此可以解出n个变元

参考代码一

#include <cstdio>

#include <cmath>

#include <cstring>

#include <iostream>

using namespace std;

const int N = 40;

int equ,var;

double a[N][N];

double x[N];

double free_x[N];

double c[15][15];

int free_num;

const double eps=1e-9;

double Gauss()

{

    int row,col,max_r;

    int i,j;

    row = col = 0;

    while(row < equ && col < var)

    {

        max_r = row;

        for(i = row+1; i < equ; i++)

            if(fabs(a[i][col])-fabs(a[max_r][col]) > eps)

                max_r = i;

        if(max_r != row)

        {

            for(j = col; j <= var; j++)

                swap(a[row][j],a[max_r][j]);

        }

        if(fabs(a[row][col]) < eps)

        {

            col++;

            continue;

        }

        for(i = row+1; i < equ; i++)

        {

            if(fabs(a[i][col]) > eps)

            {

                double t = a[i][col]/a[row][col];

                a[i][col] = 0.0;

                for(j = col+1; j <= var; j++)

                    a[i][j] -= a[row][j]*t;

            }

        }

        row++;

        col++;

    }

    //唯一解，回代

   for(int i=equ-1;i>=0;i--)

   {

       x[i]=a[i][var];

       for(int j=i+1;j<var;j++) x[i]-=a[i][j]*x[j];

       x[i]/=a[i][i];

   }

   return 0;

}

void init()

{

    memset(a,0,sizeof(a));

    memset(x,0,sizeof(x));

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        for(int i=0;i<=n;i++)

        {

            for(int j=0;j<n;j++)

            {

                scanf("%lf",&c[i][j]);

            }

        }

        for(int i=1;i<=n;i++)

        {

            for(int j=0;j<n;j++)

            {

                a[i-1][j]=2*(c[i][j]-c[i-1][j]);

            }

            a[i-1][n]=0;

            for(int j=0;j<n;j++) a[i-1][n]+=(c[i][j]+c[i-1][j])*(c[i][j]-c[i-1][j]);

        }

        equ=n;var=n;

        Gauss();

        for(int i=0;i<n;i++)

        {

            if(i) printf(" ");

            printf("%.3f",x[i]);

        }

    }

    return 0;

}

参考代码二

/**************************************************************

	Problem: 1013

	User: yueguang12

	Language: C++

	Result: Accepted

	Time:0 ms

	Memory:1296 kb

****************************************************************/

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 30005

using namespace std;

int read(){

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

void Out(ll a){

    if(a<0) putchar('-'),a=-a;

    if(a>=10) Out(a/10);

    putchar(a%10+'0');

}

const int N=15;

double a[N][N];

double c[15][15];

const double eps=1e-9;

int n;

bool Gauss(){

     int now=1,to;double t;

     for(int i=1;i<=n;i++){

         for(to=now;to<=n;to++)if(fabs(a[to][i])>eps)break;

         if(to>n)continue;

         if(to!=now)for(int j=1;j<=n+1;j++)

            swap(a[to][j],a[now][j]);

         t=a[now][i];

         for(int j=1;j<=n+1;j++)a[now][j]/=t;

         for(int j=1;j<=n;j++) if(j!=now){

             t=a[j][i];

             for(int k=1;k<=n+1;k++)

                a[j][k]-=t*a[now][k];

        }

        now++;

     }

     for(int i=now;i<=n;i++)

        if(fabs(a[i][n+1])>eps) return 0;

     return 1;

}

void Build(){

    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)

    {

           a[i][j]=2*(c[i][j]-c[i-1][j]);

           a[i][n+1]+=(c[i][j]+c[i-1][j])*(c[i][j]-c[i-1][j]);

    }

}

int main(){

    n=read();

    for(int i=0;i<=n;i++) for(int j=1;j<=n;j++)

        scanf("%lf",&c[i][j]);

    Build();

    Gauss();

    for(int i=1;i<=n;i++){

        if(i>1) printf(" ");

        printf("%.3f",a[i][n+1]);

    }

    puts("");

    return 0;

}

巴特西

【BZOJ 1013】球形空间产生器sphere（高斯消元）

球形空间产生器sphere HYSBZ - 1013 （高斯消元）

题意

提示

解法

参考代码一

参考代码二

最新文章

热门文章