要你求出3个到那n+1个点距离相等的点的坐标,要你求出3个到那n+三个点距离相等的点的坐标

【BZOJ】1013:
[JSOI2008]球形空间发出器sphere

1013:
[JSOI2008]球形空间发出器sphere

【BZOJ】1013: [JSOI2008]球形空间发出器sphere,bzojjsoi二零一零

【BZOJ】1013: [JSOI2008]球形空间发出器sphere

题意:给n+二个n维的点的坐标,要你求出贰个到那n+二个点距离相等的点的坐标;

思路:高斯消元即第i个点和第i+3个点处理出五个架子,那样n+3个点刚刚有n个周全的n元变量,即可求解。

式子:Σ( (a[i][j] – x[j])^2 )  = Σ( a[i+1][j] – x[j])^2 )
=>Σ( x[j]*[2*(a[i+1][j]-a[i][j])] ) =
Σ(a[i+1][j]*a[i+1][j] –
a[i][j]*a[i][j]);直接预处理即可;

在意:在Gauss处理出上三角阵的长河中,每一遍要选出主对角线绝对值最大的行作为参考行,貌似是精度难点。还有正是归零的进度中,要变成参考行在消,为了不出新除0的场所。

 

图片 1#include<iostream>
#include<cstdio> #include<cstring>
#include<string.h> #include<algorithm>
#include<map> #include<queue> #include<vector>
#include<cmath> #include<stdlib.h> #include<time.h>
using namespace std; typedef long long ll; #define rep0(i,l,r) for(int
i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <=
(r);i++) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a)
memset(a,-1,sizeof(a)) double a[11][11],A[12][12]; int n; void
Gauss() { int i,j,k; rep1(i,1,n){ int mx = i; rep1(j,i+1,n)
if(fabs(A[mx][i]) < fabs(A[j][i])) mx = j; rep1(j,i,n+1)
swap(A[mx][j],A[i][j]); rep1(j,i+1,n)if(A[i][i] != 0){
double y = A[j][i]/A[i][i]; rep1(k,i,n+1) A[j][k] -=
y*A[i][k]; } } for(int i = n;i >= 1;i–){ rep1(j,i+1,n)
A[i][n+1] -= A[i][j] * A[j][n+1]; A[i][n+1] /=
A[i][i]; //化为周详为1;保证有解,则A[i][i] != 0; } } int main()
{ int i,j; scanf(“%d”,&n); rep1(i,1,n+1) rep1(j,1,n)
scanf(“%lf”,&a[i][j]); rep1(i,1,n) rep1(j,1,n){ A[i][j] =
2*(a[i+1][j] – a[i][j]); A[i][n+1] +=
a[i+1][j]*a[i+1][j] – a[i][j]*a[i][j]; } Gauss();
printf(“%.3f”,A[1][n+1]); rep1(i,2,n) printf(” %.3f”,A[i][n+1]);
} View Code

 

http://www.bkjia.com/Cyy/1098070.htmlwww.bkjia.comtruehttp://www.bkjia.com/Cyy/1098070.htmlTechArticle【BZOJ】1013:
[JSOI2008]球形空间发出器sphere,bzojjsoi2009 【BZOJ】1013:
[JSOI2008]球形空间发出器sphere
题意:给n+3个n维的点的坐标,要你求出1个到…

题意:给n+叁个n维的点的坐标,要你求出1个到那n+一个点离开相等的点的坐标;

题意:给n+3个n维的点的坐标,要你求出3个到那n+2个点离开相等的点的坐标;

思路:高斯消元即第i个点和第i+二个点处理出一个架子,那样n+三个点恰恰有n个周详的n元变量,即可求解。

思路:高斯消元即第i个点和第i+三个点处理出2个姿态,那样n+三个点恰恰有n个全面的n元变量,即可求解。

式子:Σ( (a[i][j] – x[j])^2 )  = Σ(
a[i+1][j] – x[j])^2 )

式子:Σ( (a[i][j] – x[j])^2 ) = Σ(
a[i+1][j] – x[j])^2 )

=>   Σ( x[j]*[2*(a[i+1][j]-a[i][j])] ) = Σ(a[i+1][j]*a[i+1][j] – a[i][j]*a[i][j]);直接预处理即可;

=> Σ( x[j]*[2*(a[i+1][j]-a[i][j])] ) = Σ(a[i+1][j]*a[i+1][j] – a[i][j]*a[i][j]);直接预处理即可;

在意:在Gauss处理出上三角阵的进程中,每一趟要选出主对角线相对值最大的行作为参考行,貌似是精度难题。还有正是归零的经过中,要变成参考行再消,为了不出现除0的情景。

小心:在Gauss处理出上三角阵的历程中,每一次要选出主对角线相对值最大的行作为参考行,貌似是精度难点。还有便是归零的进程中,要变成参考行再消,为了不出现除0的景况。

 

图片 2图片 3

图片 4图片 5

#include<iostream>#include<cstdio>#include<cstring>#include<string.h>#include<algorithm>#include<map>#include<queue>#include<vector>#include<cmath>#include<stdlib.h>#include<time.h>using namespace std;typedef long long ll;#define rep0 for(int i = ;i < #define rep1 for(int i = ;i <= #define MS0 memset(a,0,sizeof#define MS1 memset(a,-1,sizeofdouble a[11][11],A[12][12];int n;void Gauss(){    int i,j,k;    rep1(i,1,n){        int mx = i;        rep1(j,i+1,n) if(fabs < fabs mx = j;        rep1(j,i,n+1) swap(A[mx][j],A[i][j]);        rep1(j,i+1,n)if(A[i][i] != 0){            double y = A[j][i]/A[i][i];            rep1(k,i,n+1) A[j][k] -= y*A[i][k];        }    }    for(int i = n;i >= 1;i--){        rep1(j,i+1,n)   A[i][n+1] -= A[i][j] * A[j][n+1];        A[i][n+1] /= A[i][i];   //化为系数为1;保证有解,则A[i][i] != 0;    }}int main(){    int i,j;    scanf("%d",&n);    rep1(i,1,n+1)        rep1(j,1,n)            scanf("%lf",&a[i][j]);    rep1(i,1,n)        rep1(j,1,n){            A[i][j] = 2*(a[i+1][j] - a[i][j]);            A[i][n+1] += a[i+1][j]*a[i+1][j] - a[i][j]*a[i][j];        }    Gauss();    printf("%.3f",A[1][n+1]);    rep1(i,2,n) printf(" %.3f",A[i][n+1]);}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
using namespace std;
typedef long long ll;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
double a[11][11],A[12][12];
int n;
void Gauss()
{
    int i,j,k;
    rep1(i,1,n){
        int mx = i;
        rep1(j,i+1,n) if(fabs(A[mx][i]) < fabs(A[j][i])) mx = j;
        rep1(j,i,n+1) swap(A[mx][j],A[i][j]);
        rep1(j,i+1,n)if(A[i][i] != 0){
            double y = A[j][i]/A[i][i];
            rep1(k,i,n+1) A[j][k] -= y*A[i][k];
        }
    }
    for(int i = n;i >= 1;i--){
        rep1(j,i+1,n)   A[i][n+1] -= A[i][j] * A[j][n+1];
        A[i][n+1] /= A[i][i];   //化为系数为1;保证有解,则A[i][i] != 0;
    }
}
int main()
{
    int i,j;
    scanf("%d",&n);
    rep1(i,1,n+1)
        rep1(j,1,n)
            scanf("%lf",&a[i][j]);
    rep1(i,1,n)
        rep1(j,1,n){
            A[i][j] = 2*(a[i+1][j] - a[i][j]);
            A[i][n+1] += a[i+1][j]*a[i+1][j] - a[i][j]*a[i][j];
        }
    Gauss();
    printf("%.3f",A[1][n+1]);
    rep1(i,2,n) printf(" %.3f",A[i][n+1]);
}

View Code

View Code

 

相关文章