QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#194789 | #7521. Find the Gap | ucup-team484# | WA | 0ms | 3728kb | C++17 | 2.1kb | 2023-09-30 22:28:13 | 2023-09-30 22:28:14 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
template<class T> struct Point3D {
typedef Point3D P;
typedef const P& R;
T x, y, z;
explicit Point3D(T x=0, T y=0, T z=0) : x(x), y(y), z(z) {}
P operator+(R p) const { return P(x+p.x, y+p.y, z+p.z); }
P operator-(R p) const { return P(x-p.x, y-p.y, z-p.z); }
T dot(R p) const { return x*p.x + y*p.y + z*p.z; }
P cross(R p) const {
return P(y*p.z - z*p.y, z*p.x - x*p.z, x*p.y - y*p.x);
}
};
typedef Point3D<ll> P3;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
if (n <= 3) {
cout << "0.0\n";
return 0;
}
vector<P3> a(n);
for (int i = 0; i < n; i++)
cin >> a[i].x >> a[i].y >> a[i].z;
ld ans = 1e18;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = i + 1; k < n; k++) {
if (k == i || k == j) continue;
for (int l = k + 1; l < n; l++) {
if (l == i || l == j) continue;
P3 dir = (a[j] - a[i]).cross(a[k] - a[l]);
int x1 = 0, x2 = 0;
int y1 = 0, y2 = 0;
for (int m = 0; m < n; m++) {
ll v1 = dir.dot(a[m] - a[i]);
ll v2 = dir.dot(a[m] - a[l]);
x1 += v1 > 0; y1 += v1 < 0;
x2 += v2 > 0; y2 += v2 < 0;
}
if (x1 > 0 && y1 > 0 || x2 > 0 && y2 > 0)
continue;
ld len = sqrtl(dir.x * dir.x + dir.y * dir.y + dir.z * dir.z);
ans = min(ans, (ld)abs(dir.dot(a[i] - a[k])) / len);
}
}
for (int k = j + 1; k < n; k++) {
P3 dir = (a[j] - a[i]).cross(a[k] - a[i]);
int x = 0, y = 0;
ld cur = 0, len = sqrtl(dir.x * dir.x + dir.y * dir.y + dir.z * dir.z);
for (int l = 0; l < n; l++) {
ll val = dir.dot(a[l] - a[i]);
x += val < 0;
y += val > 0;
cur = max(cur, (ld)abs(val) / len);
}
if (x > 0 && y > 0)
continue;
ans = min(ans, cur);
}
}
}
cout << fixed << setprecision(15) << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3728kb
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.000000000000000
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '0.0000000', error = '1.0000000'