QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#197763 | #7521. Find the Gap | ayersz | WA | 1ms | 3600kb | C++20 | 3.6kb | 2023-10-02 19:36:48 | 2023-10-02 19:36:49 |
Judging History
answer
/*
*@author:Ayersz127
*@time: 2023-10-02
*/
#include <bits/stdc++.h>
// #define MULTITEST
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using ld = long double;
template <typename T>
bool cmax(T &x, const T &y) {
return x < y ? x = y, 1 : 0;
}
template <typename T>
bool cmin(T &x, const T &y) {
return x > y ? x = y, 1 : 0;
}
const int N = 55;
struct point {
ld x, y, z;
point(ld x = 0, ld y = 0, ld z = 0) : x(x), y(y), z(z) {}
point operator-(const point &rhs) const {
return point(x - rhs.x, y - rhs.y, z - rhs.z);
}
ld len() const {
return sqrt(x * x + y * y + z * z);
}
} p[N];
using vec = point;
const ld EPS = 1e-10;
int sgn(ld x) {
if (std::abs(x) < EPS) {
return 0;
} else {
return x < 0 ? -1 : 1;
}
}
vec crs(vec a, vec b) {
return vec(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - b.x * a.y);
}
int n;
void solve(int tc) {
std::cin >> n;
for (int i = 0; i < n; i++) {
std::cin >> p[i].x >> p[i].y >> p[i].z;
}
// 三点搞一个面
ld ans = 1e18;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
vec v0 = p[j] - p[i], v1 = p[k] - p[i];
vec h = crs(v0, v1);
ld A = h.x, B = h.y, C = h.z, D0, dis = 0;
D0 = -A * p[i].x - B * p[i].y - C * p[i].z;
int f = 0;
bool flag = 1;
for (int t = 0; t < n; t++) {
double D1 = -A * p[t].x - B * p[t].y - C * p[t].z;
if (sgn(D0 - D1) == 0) {
continue;
}
if (f == 0) {
f = (D0 > D1) ? 1 : -1;
}
if ((D0 > D1 && f == -1) || (D0 < D1 && f == 1)) {
flag = 0;
break;
}
dis = std::max(dis, std::abs(D0 - D1) / h.len());
}
if (flag) {
ans = std::min(ans, dis);
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = 0; k < n; k++) {
for (int t = k + 1; t < n; t++) {
vec v0 = p[j] - p[i], v1 = p[t] - p[k];
vec h = crs(v0, v1);
ld A = h.x, B = h.y, C = h.z, D0, D1;
D0 = -A * p[i].x - B * p[i].y - C * p[i].z;
D1 = -A * p[k].x - B * p[k].y - C * p[k].z;
bool flag = true;
for (int u = 0; u < n; u++) {
ld Dx = -A * p[u].x - B * p[u].y - C * p[u].z;
if (sgn(Dx - D0) * sgn(Dx - D1) > 0) {
flag = false;
break;
}
}
if (flag) {
ans = std::min(ans, std::abs(D0 - D1) / h.len());
}
}
}
}
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cout << std::fixed << std::setprecision(15);
int t = 1;
#ifdef MULTITEST
std::cin >> t;
#endif
for (int i = 1; i <= t; i++) {
solve(i);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3600kb
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'