【bzoj1013】球形空间产生器

  • 高斯消元重修系列第一题

这题之前做过，但是今天妹主席讲了一发矩阵相关，我突然发现。。。我好像忘了高斯消元怎么写了

这道题思路很妙：

设圆心为$(r_1,r_2,……,r_n)$,然后任选两个点$(x_1,x_2,……,x_n),(y_1,y_2,……,y_n)$，则有：

$(r_1-x_1)^2+(r_2-x_2)^2+……+(r_n-x_n)^2=(r_1-y_1)^2+(r_2-y_2)^2+……+(r_n-y_n)^2$

展开后可将$r$的二次项消掉：$2(y_1-x_1)r_1+2(y_2-x_2)r_2+……+2(y_n-x_n)r_n=(y_1^2-x_1^2)+(y_2^2-x_2^2)+……+(y_n^2-x_n^2)$

使用高斯消元即可解出圆心坐标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
#define FILE "read"
#define eps 1e-6
using namespace std;
double f[15],a[15][15];
int n;
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)  scanf("%lf",&f[i]);
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){
		double x;scanf("%lf",&x);
		a[i][j]=2*(x-f[j]);  a[i][n+1]+=x*x-f[j]*f[j];
	}
}
bool gauss(){
	int now=1;
	for(int i=1,temp;i<=n;++i){
		for(temp=now;temp<=n;++temp) if(fabs(a[temp][i])>eps) break;
		if(temp>n)  continue;
		if(temp!=now)  for(int j=1;j<=n+1;++j)  swap(a[temp][j],a[now][j]);
		double 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){
			double 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 output(){
	for(int i=1;i<=n-1;++i)  printf("%.3lf ",a[i][n+1]);
	printf("%.3lf",a[n][n+1]);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	init();
	gauss();
	output();
	return 0;
}

本文标题:【bzoj1013】球形空间产生器

文章作者:chty

发布时间:2017年03月10日 - 20时05分

最后更新:2018年03月02日 - 18时10分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,