[JSOI2008] 球形空间产生器

    xiaoxiao2021-03-26  7


    题目描述

    火星人不能忍受地球人对他们的歧视,终于发明了一种非常强大的武器: 球 形空间产生器 。球形空间产生器能产生一个 N 维球体屏障,而且这个屏障是坚 不可摧的,被困在球体内的地球人就被切断了与外界的联系。Js08 现在就被困在 了屏障中,情况十分危急,必须尽快找出并摧毁球形空间产生器。Js08 经过摸索 和碰壁,给出了球体上 N+1 个点的坐标,希望你能够帮 Js08 找出球形空间产生 器的位置——它总是位于球形空间的球心。 球体定义为到空间中定点距离等于定长的点的集合。此外,空间中两点的距 离定义为:

    Distance[(x1,x2,...,xn),(y1,y2,...,yn)]=i=1n(xiyi)2


    输入格式

    输入文件第一行为整数 N,代表了空间的维度。 接下来 N+1 行,每行 N 个实数代表一个坐标。输入数据精确到小数点后 6 位。 输入数据保证输出结果唯一。


    输出格式

    输出一行 N 个实数代表球心的坐标,精确到小数点后三位。相邻 的数字之间用一个空格分开(行末无空格)


    样例数据

    样例输入

    样例数据#1 2 0.0 0.0 -1.0 1.0 1.0 0.0 样例数据#2 4 24.720172 14.560868 7.592580 25.639614 24.275281 8.136164 21.498302 -12.570364 33.948090 10.669582 4.705742 -2.648426 -22.717309 3.519597 16.222675 2.425559 -9.593546 18.349904 -15.757415 10.414070

    样例输出

    样例数据#1 0.500 1.500 样例数据#2 5.360 5.443 6.078 4.669


    数据规模

    对于 40%的数据,有 N<=3。 对于 100%的数据,有 N<=10。 对于 100%的数据,输入中数字的绝对值不超过 20000。


    题目分析

    用二维距离,就有三个坐标,假设圆心坐标为(x0,y0),球的半径为r 则有:

    (x1x0)2+(y1y0)2=r2(x2x0)2+(y2y0)2=r2(x3x0)2+(y3y0)2=r2 联立可得 (x1x0)2+(y1y0)2=(x2x0)2+(y2y0)2(x2x0)2+(y2y0)2=(x3x0)2+(y3y0)2 展开得 2x0(x1x2)+2y0(y1y2)=x21x22+y21y222x0(x2x3)+2y0(y2y3)=x22x23+y22y23 类推至n维,然后就交给贾老二解方程了


    源代码

    #include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } int n; double a[105][105],Ans[105],x[105][105]; void Simplify(int Line) { //对于行化简 int Row=Line; //1.选主元(系数绝对值最大) double Max=abs(a[Row][Line]); for(int i=Line+1; i<=n; i++) if(abs(a[i][Line])>Max) { Max=abs(a[i][Line]); Row=i; } if(Row!=Line) //2.交换行(将主元调到当前行) for(int i=Line; i<=n+1; i++)swap(a[Line][i],a[Row][i]); for(int i=Line+1; i<=n; i++) { //3.化简该行 double Multiple=a[i][Line]/a[Line][Line]; for(int j=Line; j<=n+1; j++)a[i][j]-=a[Line][j]*Multiple; } } void Gauss() { for(int i=1; i<=n; i++)Simplify(i); for(int i=n; i>=1; i--) { //从最后一个方程回代 for(int j=i+1; j<=n; j++)a[i][n+1]-=a[i][j]*Ans[j]; Ans[i]=a[i][n+1]/a[i][i]; } } int main() { scanf("%d",&n); for(int i=1; i<=n+1; i++) for(int j=1; j<=n; j++)scanf("%lf",&x[i][j]); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { a[i][n+1]+=x[i][j]*x[i][j]-x[i+1][j]*x[i+1][j]; a[i][j]=2*(x[i][j]-x[i+1][j]); } Gauss(); for(int i=1; i<=n; i++)printf("%0.3lf ",Ans[i]); return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-600326.html

    最新回复(0)