Tang-Dreamoon's Blog

bzoj 1013 球形空间产生器sphere

发表于 | 分类于 ，

bzoj什么时候可以忽略行末空格和回车啊？！

　　题目链接：bzoj 1013

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：高斯消元模板题——直接消元啊？！好吧还是需要化简一下的。显然对于一个球来说，圆心到球面上每一个点的距离都一样。所以我们可以列出一系列等式：(X-X1)^2+(Y-Y1)^2=(X-X2)^2+(Y-Y2)^2 化简一下就可以得到：2(X2-X1)X+2(Y2-Y1)Y=-X1^2+X2^2-Y1^2+Y2^2，然后直接消元求解就可以求出X、Y、Z、W……了

　　我思故我在：小心 PE 还是不要挑战 OJ 的底线为妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
double map[16][16];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n+1;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%lf",&map[i][j]);
		}
		if(i>1)
		{
			for(int j=1;j<=n;j++)
			{
				map[i-1][n+1]+=map[i][j]*map[i][j]-map[i-1][j]*map[i-1][j];
				map[i-1][j]=2*(map[i][j]-map[i-1][j]);
			}
		}
	}
	int now=1;
	for(int i=1;i<=n;i++)
	{
		bool flag=0;
		int where;
		for(int j=now;j<=n;j++)
		{
			if(map[j][i]!=0)
			{
				flag=1,where=j;
				break;
			}
		}
		if(flag)
		{
			for(int k=i;k<=n+1;k++)
				swap(map[now][k],map[where][k]);
			for(int j=1;j<=n;j++)
			{
				if(j!=now&&map[j][i]!=0)
				{
					double fuck=-map[j][i]/map[now][i];
					for(int k=i;k<=n+1;k++)
						map[j][k]+=map[now][k]*fuck;
				}
			}
			now++;
		}
	}
	printf("%.3lf",(map[1][n+1]/map[1][1]));
	for(int i=2;i<=n;i++)
		printf(" %.3lf",(map[i][n+1]/map[i][i]));
	return 0;
}