LG4035/BZOJ1013 「JSOI2008」球形空间产生器高斯消元

问题描述

LG4035

BZOJ1013

题解

设答案为\((p_1,p_2,p_3,...,p_n)\)

因为是一个球体，令其半径为\(r\)，则有

\[\sum_{i=1}^{n}{(a_i-p_i)}^2={\rm dis}^2
\]

拆式子可得

\[\sum_{i=1}^{n}a_i^2-2\times\sum_{i=1}^{n}{a_ip_i}=\sum_{i=1}^{n}p_i^2-{\rm dis}^2
\]

于是可以构造出新的方程矩阵：

\[f_{i,j}=2 \times (a_{i+1,j}-a_{i,j})
\]

\[f_{i,n+1}=\sum_{j=1}^n a_{i+1,j}^2-a_{i,j}^2
\]

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

void read(int &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-') fh=-1,ch=getchar();

	else fh=1;

	while(ch>='0'&&ch<='9'){

		x=(x<<1)+(x<<3)+ch-'0';

		ch=getchar();

	}

	x*=fh;

}

#define maxn 107

int n;

double a[maxn][maxn],bf[maxn][maxn];

int pla;

int main(){

	ios::sync_with_stdio(0);

	cin>>n;

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

		for(register int j=1;j<=n;j++) cin>>bf[i][j];

	}

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

		for(register int j=1;j<=n;j++){

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

			a[i][n+1]+=bf[i+1][j]*bf[i+1][j]-bf[i][j]*bf[i][j];

		}

	}

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

		pla=i;

		while(pla<=n&&a[pla][i]==0) pla++;

		if(pla==n+1){

			puts("No Solution");return 0;

		}

		for(register int j=1;j<=n+1;j++) swap(a[i][j],a[pla][j]);

		double tmp=a[i][i];

		for(register int j=1;j<=n+1;j++) a[i][j]=a[i][j]/tmp;

		for(register int j=1;j<=n;j++){

			if(i==j) continue;

			double rp=a[j][i];

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

				a[j][k]=a[j][k]-rp*a[i][k];

			}

		}

	}

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

		cout<<fixed<<setprecision(3)<<a[i][n+1]<<" ";

	}

	return 0;

}

巴特西

LG4035/BZOJ1013 「JSOI2008」球形空间产生器高斯消元

问题描述

题解

最新文章

热门文章

巴特西

LG4035/BZOJ1013 「JSOI2008」球形空间产生器 高斯消元

问题描述

题解

最新文章

热门文章

LG4035/BZOJ1013 「JSOI2008」球形空间产生器高斯消元