QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546981 | #7521. Find the Gap | OIer_kzc | WA | 0ms | 1948kb | C++17 | 1.9kb | 2024-09-04 16:28:54 | 2024-09-04 16:28:55 |
Judging History
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