QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#283524 | #7521. Find the Gap | light_ink_dots# | WA | 1ms | 3916kb | C++14 | 6.6kb | 2023-12-14 18:49:59 | 2023-12-14 18:49:59 |
Judging History
answer
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
using ld = long double;
int n;
const ld eps = 1e-9;
#define lt(x, y) ((x) < (y)-eps)
#define gt(x, y) ((x) > (y) + eps)
#define le(x, y) ((x) <= (y) + eps)
#define ge(x, y) ((x) >= (y)-eps)
#define eq(x, y) (le(x, y) && ge(x, y))
#define dot(x, y, z) (((y) - (x)) * ((z) - (x)))
#define cross(x, y, z) (((y) - (x)) ^ ((z) - (x)))
#define triple(x, y, z) ((x) * ((y) ^ (z)))
struct vec3 {
ld x, y, z;
vec3(ld x0 = 0, ld y0 = 0, ld z0 = 0) : x(x0), y(y0), z(z0) {}
vec3* read() {
scanf("%lf%lf%lf", &x, &y, &z);
return this;
}
inline vec3 operator-() const { return vec3(-x, -y, -z); }
inline vec3 operator+(const vec3& B) const { return vec3(x + B.x, y + B.y, z + B.z); }
inline vec3 operator-(const vec3& B) const { return vec3(x - B.x, y - B.y, z - B.z); }
inline vec3 operator*(ld k) const { return vec3(x * k, y * k); }
inline vec3 operator/(ld k) const { return *this * (1.0 / k); }
inline ld operator*(const vec3& B) const { return x * B.x + y * B.y + z * B.z; }
inline vec3 operator^(const vec3& B) const {
return vec3(y * B.z - z * B.y, z * B.x - x * B.z, x * B.y - y * B.x);
}
inline ld norm2() const { return x * x + y * y + z * z; }
inline ld norm() const { return sqrt(x * x + y * y + z * z); }
inline bool operator<(const vec3& B) const {
return lt(x, B.x) || le(x, B.x) && (lt(y, B.y) || le(y, B.y) && lt(z, B.z));
}
inline bool operator==(const vec3& B) const { return eq(x, B.x) && eq(y, B.y) && eq(z, B.z); }
};
// Positive if Right-hand rule
inline ld volume(const vec3 A, const vec3 B, const vec3 C, const vec3 D) {
return triple(B - A, C - A, D - A);
}
struct line3 {
vec3 P, t;
line3(vec3 _P = vec3(), vec3 _t = vec3()) : P(_P), t(_t) {}
};
inline ld dis2(const vec3 P, const line3 l) { return ((P - l.P) ^ l.t).norm2() / l.t.norm2(); }
struct plane {
ld A, B, C, D; // Ax + By + Cz + D = 0
plane(ld A0 = 0.0, ld B0 = 0.0, ld C0 = 0.0, ld D0 = 0.0) : A(A0), B(B0), C(C0), D(D0) {}
plane(const vec3& u, const vec3& v, const vec3& w) {
vec3 t = (v - u) ^ (w - u);
A = t.x, B = t.y, C = t.z, D = -triple(u, v, w);
} // > 0 if it follows Right-hand rule
inline vec3 normVec() const { return vec3(A, B, C); }
inline ld norm2() const { return A * A + B * B + C * C; }
inline ld operator()(const vec3& P) const { return A * P.x + B * P.y + C * P.z + D; }
};
inline ld dis2(const vec3 P, const plane F) { return F(P) * F(P) / F.norm2(); }
bool pd(vec3 a, vec3 b, vec3 c) {
return 0;
ld A = fabs((a - b) * (c - b));
ld B = fabs((a - b).norm() * (c - b).norm());
if (fabs(A - B) < eps)
return 1;
return 0;
}
vec3 p[1000];
int32_t main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> p[i].x >> p[i].y >> p[i].z;
}
ld ans = 1e18;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
for (int k = j + 1; k <= n; k++) {
if (pd(p[i], p[j], p[k]))
continue;
int gre = 0, les = 0;
plane z(p[i], p[j], p[k]);
ld M1 = 0, M2 = 0;
for (int t = 1; t <= n; t++) {
ld pj = z(p[t]);
if (fabs(pj) > eps && pj < 0) {
M1 = max(M1, sqrt(dis2(p[t], z)));
}
if (fabs(pj) > eps && pj > 0) {
M2 = max(M2, sqrt(dis2(p[t], z)));
}
}
// if(les&&gre) continue;
// ld res=0;
// for(int t=1;t<=n;t++){
// res=max(res,sqrt(dis2(p[t],z)));
// }
ans = min(ans, M1 + M2);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (i == k || j == k || pd(p[i], p[j], p[k]))
;
int gre = 0, les = 0;
plane z(p[i], p[j], p[k]);
auto v = z.normVec();
vec3 P = p[i] + v;
z = plane(p[i], p[j], P);
ld M1 = 0, M2 = 0;
for (int t = 1; t <= n; t++) {
ld pj = z(p[t]);
if (fabs(pj) > eps && pj < 0) {
M1 = max(M1, sqrt(dis2(p[t], z)));
}
if (fabs(pj) > eps && pj > 0) {
M2 = max(M2, sqrt(dis2(p[t], z)));
}
}
ans = min(ans, M1 + M2);
z = plane(p[i], p[j], p[k] + P);
M1 = 0, M2 = 0;
for (int t = 1; t <= n; t++) {
ld pj = z(p[t]);
if (fabs(pj) > eps && pj < 0) {
M1 = max(M1, sqrt(dis2(p[t], z)));
}
if (fabs(pj) > eps && pj > 0) {
M2 = max(M2, sqrt(dis2(p[t], z)));
}
}
ans = min(ans, M1 + M2);
z = plane(p[k], p[j], p[k] + P);
M1 = 0, M2 = 0;
for (int t = 1; t <= n; t++) {
ld pj = z(p[t]);
if (fabs(pj) > eps && pj < 0) {
M1 = max(M1, sqrt(dis2(p[t], z)));
}
if (fabs(pj) > eps && pj > 0) {
M2 = max(M2, sqrt(dis2(p[t], z)));
}
}
ans = min(ans, M1 + M2);
z = plane(p[k], p[i], p[k] + P);
M1 = 0, M2 = 0;
for (int t = 1; t <= n; t++) {
ld pj = z(p[t]);
if (fabs(pj) > eps && pj < 0) {
M1 = max(M1, sqrt(dis2(p[t], z)));
}
if (fabs(pj) > eps && pj > 0) {
M2 = max(M2, sqrt(dis2(p[t], z)));
}
}
ans = min(ans, M1 + M2);
// if(les&&gre) continue;
// ld res=0;
// for(int t=1;t<=n;t++){
// res=max(res,sqrt(dis2(p[t],z)));
// }
}
}
}
if (ans == 1e18) {
cout << 0, exit(0);
}
cout << fixed << setprecision(20);
cout << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3916kb
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.00000000000000000000
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '0.0000000', error = '1.0000000'