QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#661629 | #7521. Find the Gap | NCl3 | WA | 115ms | 3996kb | C++20 | 3.7kb | 2024-10-20 17:11:25 | 2024-10-20 17:11:26 |
Judging History
answer
#include <bits/stdc++.h>
using ll = long long;
using ld = long long;
using ull = unsigned long long;
constexpr int N = 1e5 + 10;
constexpr int inf = 1e9 + 10;
constexpr ll llinf = 1e18 + 10;
constexpr int mod = 1e9 + 7;
void debug() {
std::cerr << "\n";
}
template<typename T, typename... Args>
void debug(T val, const Args&... args) {
std::cerr << val << " ";
debug(args...);
}
template<typename T>
void debug(const std::vector<T>& vec) {
for (const T& x : vec) std::cerr << x << ' ';std::cerr << "\n";
}
constexpr ld eps = 1e-9;
inline int sgn(ld x) {
return x < -eps ? -1 : x > eps;
}
inline int cmp(ld a, ld b) {
return sgn(a - b);
}
struct point {
ld x, y, z;
point() {}
point(ld _x, ld _y, ld _z) : x(_x), y(_y), z(_z) {}
point operator +(const point& t) {
return { x + t.x, y + t.y, z + t.z };
}
point operator -(const point& t) {
return { x - t.x, y - t.y, z - t.z };
}
point operator*(ld d) {
return { x * d, y * d , z * d };
}
point operator/(ld d) {
return { x / d, y / d , z / d };
}
bool operator<(point p) const
{
int c = cmp(x, p.x);
if (c)
return c == -1;
c = cmp(y, p.y);
if (c)
return c == -1;
return cmp(z, p.z) == -1;
}
bool operator==(point t) const
{
return cmp(x, t.x) == 0 && cmp(y, t.y) == 0 && cmp(z, t.z) == 0;
}
ld dot(point p) { return x * p.x + y * p.y + z * p.z; }
//点积
point det(point p) {
return { y * p.z - z * p.y, z * p.x - x * p.z, x * p.y - y * p.z };
}
//叉积
ld distTo(point p) { return (*this - p).sqrt(); }
//点距离
void read() { std::cin >> x >> y >> z; }
void write() { std::cout << "(" << x << "," << y << "," << z << ")" << "\n"; }
double sqrt() { return std::sqrt(sqr()); }
ld sqr() { return x * x + y * y + z * z; }
point unit() { return *this / sqrt(); }
};
void ncl3() {
int n;
std::cin >> n;
std::vector<point> p(n);
std::set<point> S;
for (int i = 0; i < n; i++) {
p[i].read();
int d = std::gcd(std::gcd(p[i].x, p[i].y), p[i].z);
if (p[i].x / d < 0) {
d *= -1;
}
S.insert(p[i] / d);
}
if (n == 1 || S.size() == 1) {
std::cout << std::fixed << std::setprecision(11) << 0.0 << "\n";
return;
}
std::vector<point> v;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
v.push_back(p[i] - p[j]);
}
}
int m = v.size();
double ans = inf;
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
point c = v[i].det(v[j]);
if (c.sqrt() == 0) continue;
double maxl = -inf, minl = inf;
for (int k = 0; k < n; k++) {
// c.write();
// debug(c.sqrt());
double l = c.dot(p[k]) / c.sqrt();
maxl = std::max(maxl, l);
minl = std::min(minl, l);
}
ans = std::min(ans, maxl - minl);
}
}
// debug("NCl3");
std::cout << std::fixed << std::setprecision(11) << ans << "\n";
}
/*
预处理、找性质缩小范围、集合思想、正难则反、穷举
*/
int main() {
#ifdef LOCAL
clock_t time = clock();
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
// std::cin >> t;
while (t--) {
ncl3();
}
#ifdef LOCAL
std::cout << "Time Used:" << clock() - time << "ms" << "\n";
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3912kb
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:
1.00000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
5 1 1 1 1 2 1 1 1 2 1 2 2 2 1 1
output:
0.70710678119
result:
ok found '0.707106781', expected '0.707106781', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 115ms
memory: 3996kb
input:
50 973 1799 4431 1036 1888 4509 1099 1977 4587 1162 2066 4665 1225 2155 4743 1288 2244 4821 1351 2333 4899 1414 2422 4977 1540 2600 5133 1603 2689 5211 1666 2778 5289 1729 2867 5367 1792 2956 5445 1855 3045 5523 1918 3134 5601 1981 3223 5679 2044 3312 5757 2107 3401 5835 2170 3490 5913 2296 3668 606...
output:
4290.00000000000
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '4290.0000000', error = '4290.0000000'