QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236843#7521. Find the GapsizihanWA 0ms3852kbC++141.7kb2023-11-04 10:59:432023-11-04 10:59:44

Judging History

你现在查看的是最新测评结果

  • [2023-11-04 10:59:44]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3852kb
  • [2023-11-04 10:59:43]
  • 提交

answer

#include <bits/stdc++.h>
#define db long double
using namespace std;
const int N = 51;
struct node
{
	int x, y, z;
}a[N];
db b[4][4];
db out = 1e114;
int n;
db calc(db x1, db y1, db z1, db d1, db x2, db y2, db z2)
{
	return sqrt((x1 * x2 + y1 * y2 + z1 * z2 + d1) * (x1 * x2 + y1 * y2 + z1 * z2 + d1) / (x1 * x1 + y1 * y1 + z1 * z1));
}
void guass(int i, int j, int k)
{
	b[0][0] = a[i].x, b[0][1] = a[i].y, b[0][2] = a[i].z, b[0][3] = -1;
	b[1][0] = a[j].x, b[1][1] = a[j].y, b[1][2] = a[j].z, b[1][3] = -1;
	b[2][0] = a[k].x, b[2][1] = a[k].y, b[2][2] = a[k].z, b[2][3] = -1;
	for(int i = 0;i < 3;i++)
	{
		int op = -1;
		for(int j = i;j < 3;j++)
		{
			if(b[j][i])
			{
				op = j;
				break;
			}
		}
		if(op == -1)
			return ;
		if(op != i)
			for(int j = i;j < 4;j++)
				swap(b[i][j], b[op][j]);
		db k = b[i][i];
		for(int j = i;j < 4;j++)
			b[i][j] /= k;
		for(int j = i + 1;j < 3;j++)
		{
			db k = b[j][i];
			for(int w = i;w < 4;w++)
				b[j][w] -= k * b[i][w];
		}
	}
	for(int i=2;i>=0;i--)
	{
		db w=b[i][3];
		for(int j=i-1;j>=0;j--)
			b[j][3]-=b[j][i]*w;
	}
	db x = b[0][3], y = b[1][3], z = b[2][3];
	db ans = 0, ans1 = 0;
	for(int i1 = 1;i1 <= n;i1++)
	{
		db p = calc(x, y, z, 1, a[i1].x, a[i1].y, a[i1].z);
		ans = max(ans, p);
		ans1 = min(ans1, p);
	}
	out = min(out, ans - ans1);
}
int main()
{
	scanf("%d", &n);
	for(int i = 1;i <= n;i++)
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
	for(int i = 1;i <= n;i++)
	{
		for(int j = i + 1;j <= n;j++)
			for(int k = j + 1;k <= n;k++)
				guass(i, j, k);
	}
	if(out > 1e100)
		printf("0\n");
	else
		printf("%.15Lf", out);
	return 0;
}
/*
8
1 1 1
1 1 3
1 3 1
1 3 3
3 1 1
3 1 3
3 3 1
3 3 3
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3852kb

input:

8
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

output:

0.707106781186548

result:

wrong answer 1st numbers differ - expected: '1.0000000', found: '0.7071068', error = '0.2928932'