BZOJ 1013: [JSOI2008]sphere

给n维空间一个圆的圆周上的n+1点 求圆心
设这个圆心的坐标是一个n元组(a1,a2,a3,..,an)
半径为r
n点坐标为(bi1,..,bin)
————-
距离:设两个n为空间上的点A, B的坐标为(a1, a2, …, an), (b1, b2, …, bn),则AB的距离定义为:dist = sqrt( (a1-b1)^2 + (a2-b2)^2 + … + (an-bn)^2 )
————-
可列出n+1个方程
sqr(a1 –  b11) + … = sqr(r)



化开后用分别减后一个可得n个一次方程 :
(2*b21 – 2*b11) a1 + … + b11^2 – b21^2… = 0


用高斯消元解之即可

高斯消元步骤:
考虑是n元的n个方程 其他类似
————————-

1
  
1
for
1
(
1
int
1
i = 0; i < n; ++i)//用第i个方程消除i+1~n方程中第i个未知数的系数
1
  
1
{
1
    
1
int
1
k = i;
1
    
1
double
1
mx =
1
abs
1
(f[i][i]);
1
    
1
for
1
(
1
int
1
j = i + 1; j < n; ++j)
1
      
1
if
1
(mx <
1
abs
1
(f[j][i]))
1
      
1
{
1
        
1
mx =
1
abs
1
(f[j][i]);
1
        
1
k = j;
1
      
1
}
1
    
1
for
1
(
1
int
1
2
j = 0; j <= n; ++j) swap(f[i][j], f[k][j]);
//把i~n中第i个未知数系数绝对值最大的换到第i个 用这个去消其他的 可以减少误差
1
    
1
for
1
(
1
int
1
j = i + 1; j < n; ++j)
1
    
1
{
1
      
1
double
1
t = f[j][i] / f[i][i];
1
      
1
for
1
(
1
int
1
k = i + 1; k <= n; ++k) f[j][k] -= f[i][k] * t;
1
    
1
2
}
//消。。。
1
  
1
}

————————-
然后求未知数就倒着一个个求上来就行了、
————————-

1
  
1
for
1
(
1
int
1
i = n - 1; i >= 0; --i)
1
  
1
{
1
    
1
for
1
(
1
int
1
j = i + 1; j < n; ++j) f[i][n] += ans[j] * f[i][j];
1
    
1
ans[i] = -f[i][n] / f[i][i];
1
  
1
}
1
  
1
for
1
(
1
int
1
i = 0; i < n - 1; ++i)
1
printf
1
(
1
"%.3f "
1
, ans[i]);

————————-
高斯消元在某些地方循环变量限制是<n 某些是<=n 我弄混了好几次= =。。
ps.
无解:就是出现某一行有(0,0,…,a)(a <> 0)的情况 这样就无解
无穷解:在处理第i个未知数的系数时 发现i~n的第i个未知数的系数都为0 则第i个未知数无穷解
——————code—————-

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
 
double a[15][15], f[15][15], ans[15];
int n;
 
int main()
{
  scanf(“%d”, &n);
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j < n; ++j) scanf(“%lf”, &a[i][j]);
 
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      f[i][j] = 2 * a[i + 1][j] – 2 * a[i][j],
      f[i][n] += a[i][j] * a[i][j] – a[i + 1][j] * a[i + 1][j];
 
  for (int i = 0; i < n; ++i)
  {
    int k = i;
    double mx = abs(f[i][i]);
    for (int j = i + 1; j < n; ++j)
      if (mx < abs(f[j][i]))
      {
        mx = abs(f[j][i]);
        k = j;
      }
    for (int j = 0; j <= n; ++j) swap(f[i][j], f[k][j]);
    for (int j = i + 1; j < n; ++j)
    {
      double t = f[j][i] / f[i][i];
      for (int k = i + 1; k <= n; ++k) f[j][k] -= f[i][k] * t;
    }
  }
 
  for (int i = n – 1; i >= 0; –i)
  {
    for (int j = i + 1; j < n; ++j) f[i][n] += ans[j] * f[i][j];
    ans[i] = -f[i][n] / f[i][i];
  }
  for (int i = 0; i < n – 1; ++i) printf(“%.3f “, ans[i]);
  printf(“%.3f”, ans[n – 1]);

}

BZOJ 1013: [JSOI2008]sphere》上有1条评论

发表评论