QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546981#7521. Find the GapOIer_kzcWA 0ms1948kbC++171.9kb2024-09-04 16:28:542024-09-04 16:28:55

Judging History

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

  • [2024-09-04 16:28:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:1948kb
  • [2024-09-04 16:28:54]
  • 提交

answer

#include <stdio.h>
#include <string.h>

#include <cmath>
#include <algorithm>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long LL;
typedef long double LDB;
constexpr int N = 1000005;

int n;
struct Vec {
	LL x, y, z;
	void write() {
		printf("(%lld, %lld, %lld)\n", x, y, z);
	}
	Vec operator - (const Vec &t) const {
		return (Vec){x - t.x, y - t.y, z - t.z};
	}
	Vec operator * (const Vec &t) const {
		return (Vec){y * t.z - z * t.y, z * t.x - x * t.z, x * t.y - y * t.x};
	}
	void operator += (const Vec &t) {
		x += t.x, y += t.y;
	}
	void operator -= (const Vec &t) {
		x -= t.x, y -= t.y;
	}
	LL operator & (const Vec &t) const {
		return x * t.x + y * t.y + z * t.z;
	}
	LL md2() const {
		return x * x + y * y + z * z;
	}
	LDB md() const {
		return sqrtl(x * x + y * y + z * z);
	}
} w[N];
LDB res = 1e36;

int main() {
	scanf("%d", &n);
	if (n < 4) {
		puts("0.000000000000000");
		return 0;
	}
	for (int i = 0; i < n; ++i) {
		scanf("%lld%lld%lld", &w[i].x, &w[i].y, &w[i].z);
	}
	bool yes = true;
	for (int i = 1; i < n; ++i) {
		for (int j = 1; j < n; ++j) {
			if (((w[i] - w[0]) * (w[j] - w[0])).md2()) {
				yes = false;
			}
		}
	}
	if (yes) {
		puts("0.000000000000000");
		return 0;
	}
	for (int k = 0; k < n; ++k) {
		LL maxv, minv;
		auto chk = [&](const Vec &t) {
			for (int i = 0; i < n; ++i) {
				LL v = (w[i] - w[k]) & t;
				maxv = max(maxv, v);
				minv = min(minv, v);
			}
		};
		for (int i = k + 1; i < n; ++i) {
			for (int j = k + 1; j < n; ++j) {
				if (i == j) {
					continue;
				}
				Vec m = (w[i] - w[k]) * (w[j] - w[k]);
				(w[i] - w[k]).write(), (w[j] - w[k]).write();
				maxv = minv = 0;
				chk(m);
				LOG("%lld %lld %.10Lf\n", maxv, minv, m.md());
				res = min(res, (maxv - minv) / m.md());
			}
		}
	}
	printf("%.15Lf\n", res);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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, 0, 1)
(0, 1, 0)
(0, 0, 1)
(0, 1, 1)
(0, 0, 1)
(1, 0, 0)
(0, 0, 1)
(1, 0, 1)
(0, 0, 1)
(1, 1, 0)
(0, 0, 1)
(1, 1, 1)
(0, 1, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(0, 1, 0)
(1, 0, 0)
(0, 1, 0)
(1, 0, 1)
(0, 1, 0)
(1, 1, 0)
(0, 1, 0)
(1, 1, 1)
(0, 1, 1)
(0, 0, 1)
(0, 1, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
...

result:

wrong output format Expected double, but "(0," found