BZOJ 球形空间产生器 解题报告(高斯消元)
2024-08-23 08:29:53
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1013
1013: [JSOI2008]球形空间产生器sphere
有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在,你被困在了这个n维球体中,你只知道球
面上n+1个点的坐标,你需要以最快的速度确定这个n维球体的球心坐标,以便于摧毁这个球形空间产生器。
Input
第一行是一个整数n(1<=N=10)。接下来的n+1行,每行有n个实数,表示球面上一点的n维坐标。每一个实数精确到小数点
后6位,且其绝对值都不超过20000。
Output
有且只有一行,依次给出球心的n维坐标(n个实数),两个实数之间用一个空格隔开。每个实数精确到小数点
后3位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。
Sample Input
2
0.0 0.0
-1.0 1.0
1.0 0.0
0.0 0.0
-1.0 1.0
1.0 0.0
Sample Output
0.500 1.500
我们可以知道,一个球体上所有点到球心的距离相等,因此只需要求出一个点(x1,x2,x3,...,xn),使得:
Σnj=0(ai,j-xj)2=c
其中c是常数,该方程由n+1个n元二次方程构成,不是线性方程组。但我们可以通过相邻的两个方程作差,把它变成n个n元方程,同时消去常数c
于是我们可以得到下面这个阶梯矩阵
2(a1.1-a2.1) 2(a1,2-a2,2) ... 2(a1,n-a2,n) Σnj=1(a21,j-a2 2,j)
2(a2.1-a3.1) 2(a2,2-a3,2) ... 2(a2,n-a3,n) Σnj=1(a2 2,j-a23,j)
.
.
.
2(an.1-an+1,1) 2(an,2-an+1,2) ... 2(an,n-an+1,n) Σnj=1(a2n,j-a2n+1,j)
高斯消元即可
#include<bits/stdc++.h>
using namespace std; const int maxn=+;
int n;
double a[maxn][maxn],c[maxn][maxn],b[maxn];
int main()
{
scanf("%d",&n);
for (int i=;i<=n+;i++)
for (int j=;j<=n;j++)
scanf("%lf",&a[i][j]);
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
{
c[i][j]=*(a[i][j]-a[i+][j]);
b[i]+=a[i][j]*a[i][j]-a[i+][j]*a[i+][j];
}
for (int i=;i<=n;i++)
{
for (int j=i;j<=n;j++)
if (fabs(c[j][i])>1e-){
for (int k=;k<=n;k++) swap(c[i][k],c[j][k]);
swap(b[i],b[j]);
}
for (int j=;j<=n;j++){
if (i==j) continue;
double rate=c[j][i]/c[i][i];
for (int k=i;k<=n;k++) c[j][k]-=rate*c[i][k];
b[j]-=rate*b[i];
}
}
for (int i=;i<=n;i++) printf("%.3f ",b[i]/c[i][i]);
return ;
}
最新文章
- [转] HashMap的存取之美
- 进程控制块(Process Control Block, PCB)
- Entity Framework数据库初始化四种策略
- struts2类型转换器、 类型转换错误 以及INPUT view
- Java for LeetCode 155 Min Stack
- c#怎么获取当前页面的url
- bzoj 1604 [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居(set+并查集)
- Python之路【第十三篇】:jQuery -暂无内容-待更新
- call-template和apply-templates
- Gmail邮件功能那么强大,GMail被封,在国内怎么用gmail收邮件?
- 使用spring-data-redis操作redis
- 以太坊RPC机制与API实例
- Python中的PYTHONPATH环境变量
- hadoop本地开发环境搭建
- java小白也能懂的面向对象
- Java Web之Servlet的三大作用域对象
- vue轮播图实现
- JDK中关于BIO,NIO,AIO,同步,异步介绍
- Cache雪崩效应
- proguard的简单配置说明