首页 > 代码库 > 【bzoj1013】 JSOI2008—球形空间产生器sphere
【bzoj1013】 JSOI2008—球形空间产生器sphere
www.lydsy.com/JudgeOnline/problem.php?id=1013 (题目链接)
题意:有一个n维的球体,给出球上n+1个点,求出圆心。
Solution
题中给出了对于n维空间点与点之间的距离求法。那么我们将圆心的坐标设为{x1,x2,x3……xn},那么就可以列出n个n元一次方程。
高斯消元。
代码:
// bzoj1013#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define eps 1e-7#define Pi 3.1415926535898#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=30;double ans[maxn],f[maxn],a[maxn][maxn];int n;double sqr(double x) { return x*x;}void Gauss() { for (int i=1;i<=n;i++) { int to=i+1; while (to<=n && fabs(a[to][i])<=eps) to++; if (to>n) continue; for (int j=to;j<=n;j++) { double t=a[i][i]/a[j][i]; for (int k=1;k<=n+1;k++) a[j][k]=a[j][k]*t-a[i][k]; } } for (int i=n;i>=1;i--) { double t=a[i][n+1]; for (int j=i+1;j<=n;j++) t-=ans[j]*a[i][j]; ans[i]=t/a[i][i]; }} int main() { 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 t; scanf("%lf",&t); a[i][j]=2*(t-f[j]); a[i][n+1]+=sqr(t)-sqr(f[j]); } Gauss(); for (int i=1;i<n;i++) printf("%.3lf ",ans[i]); printf("%.3lf",ans[n]); return 0;}
【bzoj1013】 JSOI2008—球形空间产生器sphere
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。